Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback
Not on the map. Why?
Abstract (arXiv)
We consider regret minimization in low-rank MDPs with fixed transition and adversarial losses. Previous work has investigated this problem under either full-information loss feedback with unknown transitions (Zhao et al., 2024), or bandit loss feedback with known transition (Foster et al., 2022). First, we improve the poly(d, A, H)T5/6 regret bound of Zhao et al. (2024) to poly(d, A, H)T2/3 for the full-information unknown transition setting, where d is the rank of the transitions, A is the number of actions, H is the horizon length, and T is the number of episodes. Next, we initiate the study on the setting with bandit loss feedback and unknown transitions. Assuming that the loss has a linear structure, we propose both model based and model free algorithms achieving poly(d, A, H)T2/3 regret, though they are computationally inefficient. We also propose oracle-efficient model-free algorithms with poly(d, A, H)T4/5 regret. We show that the linear structure is necessary for the bandit case without structure on the reward function, the regret has to scale polynomially with the number of states. This is contrary to the full-information case (Zhao et al., 2024), where the regret can be independent of the number of states even for unstructured reward function.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 28 of its 44 references that are in the map. First posted on arXiv 11 Nov 2024.
Builds on
28 of 44 references.
References · 28
- 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
- 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
- 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
- 2021The Statistical Complexity of Interactive Decision Makingcited by 208
- 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
- 2022The Role of Coverage in Online Reinforcement Learningcited by 82
- 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
- 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
- 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 49
- 2022GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyondcited by 45
- 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
- 2022On the Complexity of Adversarial Decision Makingcited by 32
16 more
- 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
- 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
- 2021A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learningcited by 24
- 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 18
- 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 17
- 2023Best of Both Worlds Policy Optimizationcited by 17
- 2022Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedbackcited by 16
- 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
- 2023Efficient Model-Free Exploration in Low-Rank MDPscited by 16
- 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 14
- 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
- 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
- 2024The Power of Resets in Online Reinforcement Learningcited by 14
- 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 12
- 2022Unified Algorithms for RL with Decision-Estimation Coefficients: PAC, Reward-Free, Preference-Based Learning, and Beyondcited by 10
- 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
Built on by
Citing papers per year: 2025: 2.
2 papers.