Online learning in MDPs with linear function approximation and bandit feedback

2020/07/03 by Gergely Neu, Neu, Gergely, Julia Olkhovskaya +1 · 2 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2007.01612

openalex publication_date 2020/07/03 · openalex created_date 2020/07/10 · openalex updated_date 2026/07/28

Abstract

We consider an online learning problem where the learner interacts with a Markov decision process in a sequence of episodes, where the reward function is allowed to change between episodes in an adversarial manner and the learner only gets to observe the rewards associated with its actions. We allow the state space to be arbitrarily large, but we assume that all action-value functions can be represented as linear functions in terms of a known low-dimensional feature map, and that the learner has access to a simulator of the environment that allows generating trajectories from the true MDP dynamics. Our main contribution is developing a computationally efficient algorithm that we call MDP-LinExp3, and prove that its regret is bounded by \widetildeO(H² T^2/3 (dK)^1/3), where T is the number of episodes, H is the number of steps in each episode, K is the number of actions, and d is the dimension of the feature map. We also show that the regret can be improved to \widetildeO(H² √(TdK)) under much stronger assumptions on the MDP dynamics. To our knowledge, MDP-LinExp3 is the first provably efficient algorithm for this problem setting.

Citations

• Online Convex Optimization in Adversarial Markov Decision Processes
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Online Learning: A Modern Introduction Using Convex Optimization
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Provably Efficient Reinforcement Learning with Linear Function Approximation

Cited by

• Reinforcement Learning from Adversarial Preferences in Tabular MDPs
• Quantum Algorithm for Apprenticeship Learning

Related

• Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback
• Online Markov Decision Processes with Aggregate Bandit Feedback
• Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation
• Learning in Online MDPs: Is there a Price for Handling the Communicating Case?
• Fast rates for online learning in Linearly Solvable Markov Decision Processes