Research map / Bandits and online learning / RL theory and MDPs
Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs
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 HF-OPPO-style occupancy-measure policy search with high-order moment variance estimation to achieve the first horizon-free regret bound for adversarial linear mixture MDPs under full-information feedback.
Problem
Whether horizon-free (poly-log in H) regret is achievable for episodic RL with adversarially changing rewards and linear mixture transitions, where prior adversarial methods incur polynomial dependence on H.
Approach
Runs online mirror descent on occupancy measures (not value-based policy optimization) constrained to a confidence set of the transition kernel, and combines it with a variance-uncertainty-aware weighted least squares estimator and a high-order moment estimator extended to stochastic policies, yielding Bernstein-type confidence sets.
Key results
- Regret upper bound of Õ((d+log(|S|^2|A|))√K) with full-information feedback, i.e. horizon-free Õ(d√K+d²) in the uniform-reward (≤1/H) setting.
- Minimax regret lower bound Ω̃(d√K) for adversarial linear mixture MDPs, showing near-optimality in d and K.
- Lower bound showing an unbounded state space yields regret asymptotically linear in √H, justifying finite |S| and the unavoidability of log|S| and log|A| terms.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| occupancy-measure-based OMD with variance-uncertainty-aware weighted regression and high-order moment estimator (proposed HF-OMD-style policy search) | adversarial linear mixture MDPs with full-information feedback · theoretical regret bound | regret upper bound order in K, d | Helped |
| replace value-function-based mirror descent with occupancy-measure-based mirror descent (using rewards as gradients) | policy update in adversarial linear mixture MDPs · theoretical regret analysis | policy-regret term I_1 order in H | Helped |
| lower bound for unbounded state space (learning-free adversarial setting) | adversarial MDPs with known transition · theoretical lower bound | regret lower bound scaling | No clear effect |
Surprising findings
- Value-function-based mirror descent (OPPO/POWERS-style) inevitably introduces polynomial H dependence, motivating the occupancy-measure approach.
- Purely adversarial rewards alone can induce a √H dependence asymptotically when |S| is unbounded.
Limitations
- Requires uniform per-step reward bound of 1/H rather than total episode reward bounded by 1.
- Requires finite state and action spaces; results have log|S| and log|A| dependence.
- Full-information feedback only; bandit feedback not addressed.
Experimental setup
Metrics: regret
Baselines: OPPO POWERS HF-UCRL-VTR+
Builds on: OPPO POWERS HOME (high-order moment estimator) VTR (value-targeted regression) HF-UCRL-VTR+
Closest papers by meaning
- 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.91)
- Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback (NeurIPS 2024 · similarity 0.90)
- Horizon-Free Regret for Linear Markov Decision Processes (ICLR 2024 · similarity 0.90)
- Logarithmic Regret for Linear Markov Decision Processes with Adversarial Corruptions (AAAI 2025 · similarity 0.89)
- Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback (ICLR 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.