mlsanityData to 7 Oct 2026

Best of Both Worlds Policy Optimization

arXiv 2302.09408 ↗First posted 18 Feb 2023cs.LG cs.AI stat.MLcited by 17

Not on the map. Why?

Abstract (arXiv)

Policy optimization methods are popular reinforcement learning algorithms in practice. Recent works have built theoretical foundation for them by proving √T regret bounds even when the losses are adversarial. Such bounds are tight in the worst case but often overly pessimistic. In this work, we show that in tabular Markov decision processes (MDPs), by properly designing the regularizer, the exploration bonus and the learning rates, one can achieve a more favorable polylog(T) regret when the losses are stochastic, without sacrificing the worst-case guarantee in the adversarial regime. To our knowledge, this is also the first time a gap-dependent polylog(T) regret bound is shown for policy optimization. Specifically, we achieve this by leveraging a Tsallis entropy or a Shannon entropy regularizer in the policy update. Then we show that under known transitions, we can further obtain a first-order regret bound in the adversarial regime by leveraging the log-barrier regularizer.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 28 of its 41 references that are in the map. First posted on arXiv 18 Feb 2023.

Builds on

28 of 41 references.

References · 28

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  3. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  4. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  5. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  6. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  7. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  8. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
  9. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  10. 2019Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneouslycited by 53
  11. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  12. 2021Impossible Tuning Made Possible: A New Expert Algorithm and Its Applicationscited by 52
16 more
  1. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  2. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 49
  3. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  4. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  5. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  6. 2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
  7. 2017An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Banditscited by 43
  8. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  9. 2020Online learning in MDPs with linear function approximation and bandit feedbackcited by 29
  10. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  11. 2022Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphscited by 26
  12. 2022Best-of-Both-Worlds Algorithms for Partial Monitoringcited by 19
  13. 2021An Algorithm for Stochastic and Adversarial Bandits with Switching Costscited by 18
  14. 2022Policy Optimization for Stochastic Shortest Pathcited by 13
  15. 2022Better Best of Both Worlds Bounds for Bandits with Switching Costscited by 13
  16. 2021Best-of-All-Worlds Bounds for Online Learning with Feedback Graphscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 5; 2024: 8; 2025: 2; 2026: 2.

17 papers.

Sort:

By area:

  1. 2024Online conformal prediction with decaying step sizescited by 53
  2. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 18
  3. 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 13
  4. 2023No-Regret Online Reinforcement Learning with Adversarial Losses and Transitionscited by 13
  5. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 12
  6. 2024uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABscited by 7
  7. 2024Towards the Transferability of Rewards Recovered via Regularized Inverse Reinforcement Learningcited by 6
  8. 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
  9. 2024LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Banditscited by 4
  10. 2024Bellman Diffusion Modelscited by 4
  11. 2023Best-of-Both-Worlds Linear Contextual Banditscited by 2
  12. 2024Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedbackcited by 2
5 more
  1. 2025Reinforcement Learning from Adversarial Preferences in Tabular MDPscited by 2
  2. 2025Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedbackcited by 2
  3. 2026Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processescited by 1
  4. 2026Achieving Optimal Static and Dynamic Regret Simultaneously in Bandits with Deterministic Lossescited by 1
  5. 2024The SMART approach to instance-optimal online learningcited by 0