Research map / Bandits and online learning / RL theory and MDPs
Rate-Optimal Policy Optimization for Linear Markov Decision Processes
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 an optimistic natural policy gradient (softmax NPG with optimistic linear function approximation) for linear MDPs that uses a reward-free warmup and restricted value functions to avoid truncation, achieving Õ(√K) regret under full-feedback adversarial losses and bandit-feedback stochastic losses.
Problem
Regret minimization in online episodic linear MDPs with policy optimization; prior policy-optimization analyses achieved only suboptimal rates in K (e.g., K^{3/4}) for adversarial losses and bandit feedback.
Approach
Combine optimistic NPG (mirror descent with softmax parametrization) with a reward-free warmup that ensures good coverage on most states, plus restricted (zero outside known states) value functions and an epoch-based bonus schedule, so truncation can be removed and the policy class stays low-capacity (O(d^2 log K) parameters), giving optimal sqrt(K) regret.
Key results
- Establishes Õ(d^2 H^{7/2} sqrt(K log A)) regret for optimistic PO in linear MDPs under full-feedback adversarial losses and bandit-feedback stochastic losses, with probability 1-4δ.
- Achieves the optimal sqrt(K) rate in the bandit-feedback stochastic setting using a policy optimization approach, improving on prior K^{3/4} bounds.
- Achieves the optimal sqrt(K) rate for adversarial losses with full feedback in linear MDPs, for which no prior optimal-rate algorithm was known.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Optimistic PO with reward-free warmup and the stated bonus update schedule | Linear MDPs with adversarial losses and full feedback · Adversarial linear MDP, full feedback | regret: \widetilde O(K^{3/4}) -> \smash{\widetilde O} (\sqrt K) | Helped |
| Use Optimistic PO with reward-free warmup and the stated bonus update schedule | Linear MDPs with stationary losses and bandit feedback · Stochastic linear MDP, bandit feedback | regret: \smash{\widetilde O} (\sqrt K) | Helped |
Limitations
- Requires large lower bound on K (K ≥ H^5 d^4 log^8(dHK/δ)) and a warmup period of K_0 episodes.
- Regret bound has large polynomial dependence on d and H (d^2 H^{7/2}).
Experimental setup
Metrics: pseudo regret
Baselines: Optimistic PO for linear MDPs with adversarial costs (K^{3/4} regret) POWERS (K^{3/4} with batching) Bandit-feedback adversarial linear MDP algorithms (K^{8/9}, K^{6/7}, K^{4/5})
Builds on: Natural policy gradient Linear MDP Reward-free exploration (CoverTraj) Optimistic policy optimization for linear MDPs
Closest papers by meaning
- Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback (ICLR 2024 · similarity 0.93)
- Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback (ICML 2025 · similarity 0.93)
- Policy-Regret Minimization in Markov Games with Function Approximation (ICML 2025 · similarity 0.90)
- Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback (NeurIPS 2025 · similarity 0.90)
- Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints (ICML 2025 · similarity 0.90)
- Achieving Tractable Minimax Optimal Regret in Average Reward MDPs (NeurIPS 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.