Research map / Bandits and online learning / RL theory and MDPs
Logarithmic Regret for Linear Markov Decision Processes with Adversarial Corruptions
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.
Proposes DW-LSVI-UCB, a double-weighted least-squares value iteration algorithm for linear MDPs with adversarially corrupted rewards, achieving gap-dependent logarithmic regret that degrades only additively with the corruption level.
Problem
Reinforcement learning with linear function approximation in linear MDPs where rewards are adversarially corrupted (total corruption C per step), aiming for logarithmic instance-dependent regret in stochastic settings that is robust to corruption.
Approach
Decouples transition and reward learning in a model-based manner: a variance-weighted regression learns transition parameters (Bernstein-type confidence), while a second regression with weights inversely tied to confidence-set width learns corrupted reward parameters, down-weighting corrupted state-action pairs; a refined analysis removes a log K factor.
Key results
- DW-LSVI-UCB attains gap-dependent regret of order d^2H^4 log^2(K/δ)/gap_min + CdH^2 (up to log terms), with corruption entering only additively.
- With no corruption (C=0), the bound improves the previous best linear MDP gap-dependent regret (He, Zhou, and Gu 2021a) by a factor of order dH/log K.
- Corollary shows that with an upper bound Ĉ on corruption, the same guarantee holds with Ĉ in place of C; if C is unknown and large, no algorithm in the class can learn.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use DW-LSVI-UCB for linear MDPs with adversarial reward corruptions | Linear MDPs · Linear MDPs with reward corruptions | gap-dependent regret: eO( d2H4 log2(1+K/δ) gapmin + CdH2) | Helped |
| use DW-LSVI-UCB with no adversarial reward corruptions (C = 0), rather than the previous best result | DW-LSVI-UCB · Linear MDPs without reward corruptions | gap-dependent regret: eO(dH/ log K) | Helped |
Surprising findings
- The corruption level enters only in lower-order terms, so the leading gap-dependent term is unaffected by corruption.
Limitations
- Leading term still has an extra log K dependence (log^2 K) versus the optimal log K; the authors note it is unclear how to remove it.
- Requires known corruption level C (or an upper bound Ĉ); if the bound is underestimated the algorithm fails.
- Analysis restricted to linear MDPs, not general function approximation.
Experimental setup
Metrics: regret (gap-dependent upper bound)
Baselines: LSVI-UCB++ (He et al. 2023) He, Zhou, and Gu 2021a Jin and Luo 2020 (tabular corrupted RL) Jin, Huang, and Luo 2021
Builds on: LSVI-UCB++ He et al. 2022 weighted regression for corrupted bandits Bernstein-type self-normalized martingale concentration (Zhou, Gu, and Szepesvár gap-dependent analysis of Yang, Yang, and Du 2021 He, Zhou, and Gu 2021a gap-dependent linear MDP regret
Closest papers by meaning
- Logarithmic Regret for Reinforcement Learning with Linear Function Approximation (ICML 2021 · similarity 0.91)
- Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback (ICLR 2024 · similarity 0.90)
- Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 2024 · similarity 0.90)
- Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback (NeurIPS 2024 · similarity 0.89)
- Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs (ICLR 2024 · similarity 0.89)
- Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification (NeurIPS 2024 · similarity 0.88)
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.