Research map / Bandits and online learning / RL theory and MDPs
Dynamic Regret of Adversarial MDPs with Unknown Transition and Linear Function Approximation
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 a two-layer online ensemble framework with occupancy-measure OMD and confidence-set transition estimation to achieve dynamic regret for adversarial episodic MDPs with unknown transitions, instantiated for tabular, linear, and linear mixture MDPs.
Problem
Learning adversarial episodic MDPs with full-information losses and unknown transitions, while handling unknown non-stationarity, measured by dynamic regret against changing comparator policies.
Approach
Decomposes dynamic regret into an exploration term (from transition confidence sets) and an adaptation term (from a two-layer Hedge ensemble over OMD base-learners on occupancy measures restricted to confidence sets), with instantiations for tabular, linear, and linear mixture MDPs that match lower bounds in K and PK-bar.
Key results
- Tabular MDP dynamic regret upper bound O(S sqrt(HAT log) + sqrt(T(H log(S^2A) + PK log T))), matching lower bound in K and PK-bar up to a factor of sqrt(S).
- Linear MDP and linear mixture MDP dynamic regret bounds O(dHS sqrt(K) + sqrt(T(H log(S^2A)+PK log T))), with lower bound Omega(dH sqrt(K) + sqrt(T(H+gamma))), optimal in d, H, K, PK-bar up to a factor of S.
- Achieves the first optimal dependence on K and PK-bar without prior knowledge of non-stationarity for adversarial MDPs with unknown transition.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the two-layer online ensemble to adapt without prior knowledge of non-stationarity | Adversarial MDPs with unknown transition · General adversarial MDPs | dynamic regret: O(√(T(H log (S2A) + P̄K log T))) | Helped |
| Use tabular confidence sets for transition estimation | Algorithm 1 · Tabular adversarial MDPs | dynamic regret: O(S√HAT log(SAT/ζ) + √(T(H log (S2A) + P̄K log T))) | Helped |
| Use linear transition estimation with linear function approximation | Algorithm 1 · Linear adversarial MDPs | dynamic regret: O(dHS√K log2(K/ζ) + √(T(H log (S2A) + P̄K log T))) | Helped |
| Use model-based transition estimation for linear mixture MDPs | Algorithm 1 · Linear mixture adversarial MDPs | dynamic regret: O(dHS√K log2(K/ζ) + √(T(H log (S2A) + P̄K log T))) | Helped |
| Replace policy optimization with an occupancy-measure-based policy update | Two-layer online ensemble for linear mixture MDPs · Linear mixture adversarial MDPs | dynamic regret dependence on K and P̄K | Helped |
| Use full linear transition estimation rather than value-targeted regression | Linear mixture MDPs · Linear mixture adversarial MDPs | occupancy measure difference: O(dHS√K log2(K/ζ)) | Helped |
| Use linear function approximation instead of tabular transition estimation | Adversarial MDPs · Linear MDPs versus tabular MDPs | transition-estimation contribution to dynamic regret: eO(HS√AK) -> eO(dHS√K) | Mixed |
Limitations
- Dependence on the number of states S is not optimal (loses a factor of sqrt(S) in tabular, S in linear settings).
- Analysis restricted to full-information feedback; bandit feedback left open.
- Proofs deferred to a longer version, so details are not fully verifiable from the conference paper.
Experimental setup
Metrics: dynamic regret static regret
Baselines: Fei et al. 2020 Zhong et al. 2021 Li, Zhao, and Zhou 2023 Rosenberg and Mansour 2019 Zhao et al. 2023
Builds on: Zhao, Li, and Zhou 2022 two-layer OMD framework Li, Zhao, and Zhou 2023 linear mixture policy optimization Jaksch et al. 2010 confidence sets Zhao et al. 2023 model-based linear mixture estimation Fei et al. 2020 dynamic regret
Closest papers by meaning
- Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs (NeurIPS 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.91)
- Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback (NeurIPS 2025 · similarity 0.90)
- Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback (ICLR 2024 · similarity 0.90)
- No-Regret Reinforcement Learning in Smooth MDPs (ICML 2024 · 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.