mlsanityData to 14 Oct 2026

Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedback

arXiv 2311.07876 ↗First posted 14 Nov 2023cs.LG cs.AI stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

In this work, we study the low-rank MDPs with adversarially changed losses in the full-information feedback setting. In particular, the unknown transition probability kernel admits a low-rank matrix decomposition citepREPUCB22, and the loss functions may change adversarially but are revealed to the learner at the end of each episode. We propose a policy optimization-based algorithm POLO, and we prove that it attains the widetildeO(K^frac56A^frac12dln(1+M)/(1-γ)2) regret guarantee, where d is rank of the transition kernel (and hence the dimension of the unknown representations), A is the cardinality of the action space, M is the cardinality of the model class, and γ is the discounted factor. Notably, our algorithm is oracle-efficient and has a regret guarantee with no dependence on the size of potentially arbitrarily large state space. Furthermore, we also prove an Omega(fracγ21-γ √d A K) regret lower bound for this problem, showing that low-rank MDPs are statistically more difficult to learn than linear MDPs in the regret minimization setting. To the best of our knowledge, we present the first algorithm that interleaves representation learning, exploration, and exploitation to achieve the sublinear regret guarantee for RL with nonlinear function approximation and adversarial losses.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 54 of its 80 references that are in the map. First posted on arXiv 14 Nov 2023.

Builds on

54 of 80 references.

References · 54

  1. 2020CURL: Contrastive Unsupervised Representations for Reinforcement Learningcited by 760
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  5. 2020Decoupling Representation Learning from Reinforcement Learningcited by 269
  6. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  7. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  8. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  9. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  10. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  11. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  12. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
38 more
  1. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
  2. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  3. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
  4. 2021Pretraining Representations for Data-Efficient Reinforcement Learningcited by 105
  5. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  6. 2021Representation Matters: Offline Pretraining for Sequential Decision Makingcited by 91
  7. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  8. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  9. 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 79
  10. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  11. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  12. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  13. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  14. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  15. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  16. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  17. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
  18. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  19. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  20. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  21. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  22. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  23. 2020Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscited by 42
  24. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  25. 2020Online learning in MDPs with linear function approximation and bandit feedbackcited by 30
  26. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  27. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 29
  28. 2020Stochastic Shortest Path with Adversarially Changing Costscited by 28
  29. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  30. 2020Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transitioncited by 27
  31. 2021A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learningcited by 24
  32. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  33. 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 19
  34. 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
  35. 2022Pretraining in Deep Reinforcement Learning: A Surveycited by 18
  36. 2022Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedbackcited by 17
  37. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 17
  38. 2019Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalitiescited by 15

50 most cited of 54 All 54 (JSON)

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 1; 2025: 2.

4 papers.

  1. 2023Provably Efficient CVaR RL in Low-rank MDPscited by 6
  2. 2025Decision Making in Hybrid Environments: A Model Aggregation Approachcited by 3
  3. 2024Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedbackcited by 2
  4. 2025An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPscited by 2