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

arXiv: https://arxiv.org/abs/2311.07876 · HTML: https://mlsanity.com/paper/2311.07876/

## 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 (most cited first, 30 of 54)

- [CURL: Contrastive Unsupervised Representations for Reinforcement Learning](https://mlsanity.com/paper/2004.04136/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Decoupling Representation Learning from Reinforcement Learning](https://mlsanity.com/paper/2009.08319/) (2020)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Optimism in Reinforcement Learning with Generalized Linear Function Approximation](https://mlsanity.com/paper/1912.04136/) (2019)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Pretraining Representations for Data-Efficient Reinforcement Learning](https://mlsanity.com/paper/2106.04799/) (2021)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Representation Matters: Offline Pretraining for Sequential Decision Making](https://mlsanity.com/paper/2102.05815/) (2021)
- [Learning Adversarial MDPs with Bandit Feedback and Unknown Transition](https://mlsanity.com/paper/1912.01192/) (2019)
- [Model-free Representation Learning and Exploration in Low-rank MDPs](https://mlsanity.com/paper/2102.07035/) (2021)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Online Convex Optimization in Adversarial Markov Decision Processes](https://mlsanity.com/paper/1905.07773/) (2019)
- [Optimistic Policy Optimization with Bandit Feedback](https://mlsanity.com/paper/2002.08243/) (2020)
- [Logarithmic Regret for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2011.11566/) (2020)
- [On Oracle-Efficient PAC RL with Rich Observations](https://mlsanity.com/paper/1803.00606/) (2018)
- [Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions](https://mlsanity.com/paper/2010.01374/) (2020)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes](https://mlsanity.com/paper/2212.06132/) (2022)
- [Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation](https://mlsanity.com/paper/2103.12923/) (2021)
- [Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses](https://mlsanity.com/paper/2107.08346/) (2021)
- [Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2205.11507/) (2022)

## Built on by (most cited first, 4 of 4)

- [Provably Efficient CVaR RL in Low-rank MDPs](https://mlsanity.com/paper/2311.11965/) (2023)
- [Decision Making in Hybrid Environments: A Model Aggregation Approach](https://mlsanity.com/paper/2502.05974/) (2025)
- [Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback](https://mlsanity.com/paper/2411.06739/) (2024)
- [An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPs](https://mlsanity.com/paper/2510.08882/) (2025)

## 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.