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 \(\widetilde\{\mathcal\{O\}\}\big(H^2 T^\{2/3\} (dK)^\{1/3\}\big)\), 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

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyneu2020online

Related papers

• Online Reinforcement Learning In Markov Decision Process Using Linear Programming (2023)3.58
• Towards Optimal Regret In Adversarial Linear Mdps With Bandit Feedback (2023)0.00
• Refined Regret For Adversarial Mdps With Linear Function Approximation (2023)0.00
• Fast Rates For Online Learning In Linearly Solvable Markov Decision Processes (2017)0.00
• Online Markov Decision Processes With Aggregate Bandit Feedback (2021)0.00
• Improved Algorithm For Adversarial Linear Mixture Mdps With Bandit Feedback And Unknown Transition (2024)0.00
• Nearly Minimax Optimal Reinforcement Learning For Linear Markov Decision Processes (2022)0.00
• Efficient Learning In Non-stationary Linear Markov Decision Processes (2020)6.77