Research map / Bandits and online learning / RL theory and MDPs
Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Improves full-information adversarial low-rank MDP regret from T^{5/6} to T^{2/3} and gives the first bandit-feedback algorithms with unknown transitions (inefficient T^{2/3} model-based/model-free, oracle-efficient T^{4/5}) under linear loss structure.
Problem
Regret minimization in adversarial low-rank MDPs with unknown transitions and unknown features, under full-information or bandit loss feedback.
Approach
A two-phase design separating reward-free representation learning (model-based or model-free, e.g., VoX/policy cover) from exponential-weights policy optimization, with a novel off-policy loss estimator that uses learned features and occupancies plus an exploration bonus; linear loss structure is used to bound the policy class size independent of states.
Key results
- Full-information model-based algorithm improves regret from T^{5/6} (Zhao et al. 2024) to Õ(H^3(d^2+|A|)T^{2/3}).
- Model-based bandit algorithm achieves Õ(d^2 H^3 |A|(d^2+|A|) T^{2/3} log|Π|) regret; with linear-loss policy cover, Õ(d^3H^3|A|(d^2+|A|)T^{2/3}).
- Oracle-efficient model-free bandit algorithm (oblivious adversary) achieves poly(A,d,H) T^{4/5} regret; without loss structure, bandit regret must scale as Ω(sqrt(|X||A|T)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Separate initial transition representation learning from policy optimization | Adversarial low-rank MDP model-based learning · Full-information feedback | regret bound: \mathcal{O}(T^{\nicefrac{5}{6}}) -> \mathrm{Reg}_T \le \otil\left(H^3 \left(d^2 + |\mathcal{A}|\right)T^{\frac{2}{3}}\ri | Helped |
| Impose linear structure on the loss function | Adversarial low-rank MDP bandit learning · Bandit feedback with unknown transitions | dependence of regret on state-space size | Helped |
| Use a model-free algorithm instead of a model-based algorithm | Adversarial low-rank MDP bandit learning · Bandit feedback with linear losses | regret bound: \mathrm{poly}(d,A,H)T^{\nicefrac{2}{3}} -> \mathrm{poly}(A,d,H,\log(|\Phi|/\delta))\cdot T^{\nicefrac{4}{5}} | Mixed |
| Use spanner policies and assume access to the loss feature | Model-free oracle-efficient bandit algorithm · Adaptive adversary | regret bound: \mathrm{poly}(A,d,H,\log(|\Phi|/\delta))\cdot T^{\nicefrac{4}{5}} | Helped |
| Remove structure from the loss function | Adversarial low-rank MDP bandit learning · Bandit feedback with unknown transitions | regret lower bound: \Omega(\sqrt{|\mathcal{X}| |\mathcal{A}| T}) | Hurt |
| Use full-information rather than bandit feedback | Adversarial low-rank MDP learning with unstructured losses · Unknown transitions | regret lower bound: \Omega(\sqrt{|\mathcal{A}| T}) vs. \Omega(\sqrt{|\mathcal{X}| |\mathcal{A}| T}) | Helped |
Surprising findings
- Without structure on the loss, bandit feedback regret must scale polynomially with the number of states, unlike full-information feedback where it can be state-independent.
- The model-free oracle-efficient bandit algorithm's T-dependence (T^{4/5}) outperforms the previous best full-information model-based bound T^{5/6}.
Limitations
- Optimal sqrt(T) regret not achieved due to two-phase design.
- Model-based and first model-free bandit algorithms are computationally inefficient.
- Bandit results require linear loss structure and realizability assumptions on function classes.
Experimental setup
Metrics: regret bound (theoretical)
Baselines: Zhao et al. (2024) Foster et al. (2022)
Builds on: Zhao et al. 2024 adversarial low-rank MDP Foster et al. 2022 low-rank MDP bandit VoX RepLearn John's exploration
Closest papers by meaning
- Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback (ICLR 2024 · similarity 0.92)
- Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback (NeurIPS 2025 · similarity 0.91)
- Dynamic Regret of Adversarial MDPs with Unknown Transition and Linear Function Approximation (AAAI 2024 · similarity 0.91)
- Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs (NeurIPS 2024 · similarity 0.90)
- Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs (ICLR 2024 · similarity 0.90)
- Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback (ICML 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.