Online learning in MDPs with linear function approximation and bandit feedback

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 $\tilde{\mathcal{O}}(H^2{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 $\tilde{\mathcal{O}}\left(H^2\sqrt{TdK}\right)$ under much stronger assumptions on the MDP dynamics. To our knowledge, MDP-LinExp3 is the first provably efficient algorithm for this problem setting.

References in corpus (8)

• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Online Learning: A Modern Introduction Using Convex Optimization
• Towards minimax policies for online linear optimization with bandit feedback
• Online Convex Optimization in Adversarial Markov Decision Processes
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Exploration-Enhanced POLITEX
• Near Optimal Policy Optimization via REPS

Cited by in corpus (8)

• Corruption-robust exploration in episodic reinforcement learning
• Nonstationary Reinforcement Learning with Linear Function Approximation
• Robust Policy Gradient against Strong Data Corruption
• Efficient Learning in Non-Stationary Linear Markov Decision Processes
• Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses
• Online Markov Decision Processes with Non-oblivious Strategic Adversary