Research map / Bandits and online learning / RL theory and MDPs
Online MDP with Prototypes Information: A Robust Adaptive Approach
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 RPO-AAS, an online robust MDP algorithm that uses a finite set of known transition prototypes and an adaptively shrinking ambiguity set to achieve sublinear regret under the true kernel, plus a non-robust variant NRPO-NPC.
Problem
Online episodic loop-free MDPs where the true transition kernel is one of finitely many known prototypes; the goal is to identify the true kernel and keep good performance (regret and worst-case value) during learning when data is limited.
Approach
Instead of a fixed-size exogenous uncertainty set, it keeps an adaptive (s,a)-rectangular ambiguity set built from prototypes, eliminating prototypes whose transition at the most-visited state-action pair deviates from the empirical estimate; each episode it plays the robust optimal policy over this shrinking set, yielding sublinear regret under the true kernel.
Key results
- RPO-AAS (RO) achieves regret bound L^2 gamma sqrt(4T|S||A| ln(3LT/delta)), matching the |S|, |A|, T dependence of UCBVI per the authors.
- In the fixed-gap setting with K=4 prototypes, NRPO-NPC, NRPO-NPC-2 and RO converge significantly faster than UCBVI in the GridWorld experiment.
- With 4 random prototypes, RO outperforms UCBVI and NRPO-NPC in the first 2,000 episodes with lower fluctuations; with 10 random prototypes, UCBVI converges to optimum faster after 2,000 episodes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RPO-AAS with fixed-gap prototypes (K=4) instead of UCBVI | Online MDP · GridWorld, fixed-gap prototypes (K=4) | average expected episode reward | Helped |
| Use RPO-AAS with fixed-gap prototypes (K=10) instead of UCBVI | Online MDP · GridWorld, fixed-gap prototypes (K=10) | average expected episode reward | Helped |
| Use RPO-AAS with fixed-gap prototypes (K=10) | Online MDP · GridWorld, fixed-gap prototypes (K=10), early episodes | average expected episode reward | Helped |
| Use RPO-AAS with random prototypes (K=4) instead of UCBVI or NRPO-NPC | Online MDP · GridWorld, random prototypes (K=4), first 2,000 episodes | average expected episode reward | Helped |
| Use RPO-AAS with random prototypes (K=4) | Online MDP · GridWorld, random prototypes (K=4) | policy reward fluctuation | Helped |
| Use prototype-informed methods, including RPO-AAS, instead of UCBVI | Online MDP · GridWorld, random prototypes (K=10), first 400 episodes | average expected episode reward | Helped |
| Use RPO-AAS with random prototypes (K=10) instead of UCBVI | Online MDP · GridWorld, random prototypes (K=10), after 2,000 episodes | average expected episode reward | Hurt |
| Use RPO-AAS with random prototypes (K=10) | Online MDP · GridWorld, random prototypes (K=10) | policy reward fluctuation | Helped |
Surprising findings
- With many random prototypes (K=10), UCBVI eventually outperforms the robust RPO-AAS after 2,000 episodes, showing diminishing benefit of prototype information.
- The heuristic NRPO-NPC-2 fails to converge to the optimal policy in the random-prototype setting.
Limitations
- Regret analysis relies on a structural assumption (Assumption 1) on prototype differences across states within a layer; random prototypes in experiments violate it.
- Experiments are limited to a single small 5x4 GridWorld with known reward and synthetic prototypes.
- Requires a known finite set of prototypes containing the true kernel.
Experimental setup
Benchmarks: GridWorld 5x4 loop-free MDP (custom)
Metrics: average expected episode reward regret
Baselines: UCBVI NRPO-NPC-2
Builds on: UCBVI occupancy measure online MDP (Rosenberg and Mansour 2019) robust MDP (Iyengar 2005; Nilim and El Ghaoui 2005) Dong et al. 2022 online robust MDP
Closest papers by meaning
- Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity (ICLR 2024 · similarity 0.90)
- Bring Your Own (Non-Robust) Algorithm to Solve Robust MDPs by Estimating The Worst Kernel (ICML 2024 · similarity 0.90)
- Policy Optimization for Robust Average Reward MDPs (NeurIPS 2024 · similarity 0.90)
- Provable Policy Gradient for Robust Average-Reward MDPs Beyond Rectangularity (ICML 2025 · similarity 0.89)
- Solving Robust Markov Decision Processes: Generic, Reliable, Efficient (AAAI 2025 · similarity 0.89)
- A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes (ICML 2024 · similarity 0.89)
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.