Research map / Bandits and online learning / RL theory and MDPs
Near-Optimal Dynamic Regret for 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 OOPE, a hybrid that pairs occupancy-measure-based two-layer global optimization with policy-based variance-aware value-targeted regression to get near-optimal dynamic regret for adversarial linear mixture MDPs with unknown transitions and no prior knowledge of the non-stationarity measure.
Problem
Dynamic regret minimization for episodic adversarial linear mixture MDPs with unknown transitions and full-information feedback, where the non-stationarity measure is unknown.
Approach
Combine an occupancy-measure-based two-layer (base-learner plus Hedge meta) global optimization over a confidence set of transitions with a policy-based variance-aware weighted ridge regression that bounds the occupancy-measure approximation error via value differences, avoiding state-size dependence.
Key results
- Upper bound of Otilde(d sqrt(H^3 K) + sqrt(HK(H + P_K))) dynamic regret for adversarial linear mixture MDPs with unknown transition and unknown non-stationarity measure, removing the state-size S dependence of prior work.
- Matching lower bound Omega(d sqrt(H^3 K) + sqrt(HK(H + P_K))) shows minimax optimality up to logarithmic factors in d, H, K and the non-stationarity measure.
- Improves H dependence over known-P_K result of Otilde(d sqrt(H^3 K) + H^2 sqrt((K+P_K)(1+P_K))).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Combine occupancy-measure-based global optimization with policy-based variance-aware value-targeted regression | OOPE for adversarial linear mixture MDPs with unknown transitions · Adversarial linear mixture MDPs, unknown transition, full information | dynamic regret upper bound: \Ot\big(dH S \sqrt{K} + \sqrt{HK(H + \Pb_K)}\big) -> \Ot\big(d \sqrt{H^3 K} + \sqrt{HK(H + \Pb_K)}\big) | Helped |
| Use OOPE without prior knowledge of the non-stationarity measure | Adversarial linear mixture MDPs · Adversarial linear mixture MDPs, unknown transition, full information | dynamic regret upper bound: \Ot\big(\sqrt{d^2 H^3 K} + H^2 \sqrt{(K + P_K)(1 + P_K)}\big) -> \Ot\big(\sqrt{d^2 H^3 K} + \sqrt{HK(H + \Pb_K)}\big) | Helped |
Limitations
- Computational cost dominated by the occupancy-measure-based component, more expensive than policy-based methods.
- Analysis assumes d >= H to simplify the bound.
- Results are theoretical with no empirical evaluation.
Experimental setup
Metrics: dynamic regret (theoretical bound)
Baselines: Zhao et al. policy optimization with restart (known P_K) Zhao et al. improved policy optimization (known P_K) Two-layer policy optimization (unknown non-stationarity) Occupancy-measure two-layer algorithm with polynomial S dependence (unknown non-
Builds on: linear mixture MDP (Ayoub et al. 2020) variance-aware weighted ridge regression (Zhou et al. 2021) Hedge / fixed-share Exp3 policy optimization occupancy-measure-based online MDP (Zimin & Neu style) two-layer online ensemble
Closest papers by meaning
- Dynamic Regret of Adversarial Linear Mixture MDPs (NeurIPS 2023 · similarity 0.96)
- Dynamic Regret of Adversarial MDPs with Unknown Transition and Linear Function Approximation (AAAI 2024 · similarity 0.93)
- Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs (ICLR 2024 · similarity 0.91)
- Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback (NeurIPS 2024 · similarity 0.90)
- Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback (NeurIPS 2025 · similarity 0.88)
- 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.