Research map / Bandits and online learning / RL theory and MDPs
Warm-up Free Policy Optimization: Improved Regret in 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 a truncation mechanism that removes the costly reward-free warm-up phase from policy optimization in linear MDPs, yielding warm-up-free PO algorithms (REPO, DEPO) with improved regret bounds.
Problem
Existing rate-optimal policy optimization algorithms for linear MDPs require a costly warm-up reward-free exploration phase that is hard to implement and unlikely to generalize beyond linear function approximation.
Approach
Replace the warm-up exploration phase with a truncation mechanism on features (indicator on feature uncertainty under the estimated covariance), combined with randomized ensemble policy optimization and multiplicative-weights hedging over perturbed-reward PO copies, to get sqrt(H^4 d^3 K)-type regret without warm-up.
Key results
- REPO achieves regret Õ(sqrt(K d^3 H^5)) with high probability under linear MDPs with bandit feedback, without a warm-up phase.
- The DEPO/REPO analysis for stochastic bandit feedback and adversarial full-information improves on the warm-up-based regret Õ(sqrt(H^7 d^4 K)) of Sherman et al. 2023a per the introduction's claims.
- For aggregate bandit feedback, the claimed regret improves from Õ(sqrt(H^9 d^5 K)) to Õ(sqrt(H^5 d^5 K)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the pure-exploration warm-up with a truncation mechanism | Proposed PO algorithm · Linear MDP, stochastic losses with bandit feedback | regret: \widetilde{O} (\sqrt{H^7 d^4 K}) -> \widetilde{O} (\sqrt{H^4 d^3 K}) | Helped |
| Replace the pure-exploration warm-up with a truncation mechanism | Proposed PO algorithm · Linear MDP, adversarial losses with full-information feedback | regret: \widetilde{O} (\sqrt{H^7 d^4 K}) -> \widetilde{O} (\sqrt{H^4 d^3 K}) | Helped |
| Replace the pure-exploration warm-up with a truncation mechanism | Proposed PO algorithm · Linear MDP, stochastic losses with aggregate bandit feedback | regret: \widetilde{O} (\sqrt{H^9 d^5 K}) -> \widetilde{O} (\sqrt{H^5 d^5 K}) | Helped |
Limitations
- Regret bound of Õ(sqrt(H^4 d^3 K)) is not improved further without variance reduction, which has not been applied to PO methods.
- Analysis assumes finite state and action spaces for exposition.
Experimental setup
Metrics: regret
Baselines: Sherman et al. 2023a LSVI-UCB RE-LSVI
Builds on: Sherman et al. 2023 policy optimization with warm-up LSVI-UCB RE-LSVI
Closest papers by meaning
- Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback (ICLR 2024 · similarity 0.89)
- Rate-Optimal Policy Optimization for Linear Markov Decision Processes (ICML 2024 · similarity 0.88)
- Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints (ICML 2025 · similarity 0.88)
- Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes (AAAI 2024 · similarity 0.88)
- Horizon-Free Regret for Linear Markov Decision Processes (ICLR 2024 · similarity 0.87)
- Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs (ICLR 2024 · similarity 0.87)
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.