Emergence of Exploration in Policy Gradient Reinforcement Learning via Retrying

• URL: http://arxiv.org/abs/2606.00151v1
• Date: Fri, 29 May 2026 03:35:13 GMT
• Title: Emergence of Exploration in Policy Gradient Reinforcement Learning via Retrying
• Abstract summary: ReMax is an objective that evaluates a policy by the expected maximum return over $M$ samples, where $M$ is a positive integer, while accounting for return uncertainty.<n>For efficient policy optimization, we derive a new policy-gradient formulation for ReMax and introduce ReMax PPO (RePPO), a PPO variant that optimize ReMax while generalizing the discrete retry count $M$ to a continuous parameter $m > 0$, enabling fine-grained control of exploration.<n> Empirically, RePPO promotes exploration, without any explicit exploration bonuses, on the MinAtar and Craftax benchmarks.
• Score: 28.212141160523178
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In reinforcement learning (RL), agents benefit from exploration only because they repeatedly encounter similar states: trying different actions can improve performance or reduce uncertainty; without such retries, a greedy policy is optimal. We formalize this intuition with ReMax, an objective that evaluates a policy by the expected maximum return over $M$ samples, where $M$ is a positive integer, while accounting for return uncertainty. Optimizing this objective induces stochastic exploration as an emergent property, without explicit bonus terms. For efficient policy optimization, we derive a new policy-gradient formulation for ReMax and introduce ReMax PPO (RePPO), a PPO variant that optimizes ReMax while generalizing the discrete retry count $M$ to a continuous parameter $m > 0$, enabling fine-grained control of exploration. Empirically, RePPO promotes exploration, without any explicit exploration bonuses, on the MinAtar and Craftax benchmarks.

Related papers

• Retry Policy Gradients in Continuous Action Spaces [3.78414997207345]
  We introduce pathwise derivative estimators for retry objectives and use them to extend ReMax to continuous action spaces.<n>We show that ReMax can encourage exploration by reshaping the policy-gradient landscape.<n>We instantiate this objective as ReMax Actor-Critic (ReMAC), an off-policy actor--critic algorithm.
  arXiv  Detail & Related papers  (2026-06-04T08:57:45Z)
• Improved Bounds for Reward-Agnostic and Reward-Free Exploration [5.120675183010349]
  We study reward-free and reward-agnostic exploration in episodic finite-horizon Markov decision processes.<n> Reward-free exploration aims to enable $$-optimal policies for any reward revealed after exploration, while reward-agnostic exploration targets $$-optimality for rewards drawn from a small finite class.
  arXiv  Detail & Related papers  (2026-02-18T11:04:15Z)
• Intrinsic Reward Policy Optimization for Sparse-Reward Environments [1.9336815376402718]
  Intrinsic rewards can provide principled guidance for exploration.<n>We propose a policy optimization framework that leverages multiple intrinsic rewards to directly optimize a policy.<n>Our algorithm -- intrinsic reward policy optimization (IRPO) -- achieves this by using a surrogate policy gradient.
  arXiv  Detail & Related papers  (2026-01-29T08:25:14Z)
• Asymmetric REINFORCE for off-Policy Reinforcement Learning: Balancing positive and negative rewards [17.695285420477035]
  We study the intermediate range of algorithms between off-policy RL and supervised fine-tuning.<n>We first provide a theoretical analysis of this off-policy REINFORCE algorithm.<n>Our analysis reveals that while on-policy updates can safely leverage both positive and negative signals, off-policy updates benefit from focusing more on positive rewards than on negative ones.
  arXiv  Detail & Related papers  (2025-06-25T15:07:16Z)
• Accelerating RL for LLM Reasoning with Optimal Advantage Regression [52.0792918455501]
  We propose a novel two-stage policy optimization framework that directly approximates the optimal advantage function.<n>$A$*-PO achieves competitive performance across a wide range of mathematical reasoning benchmarks.<n>It reduces training time by up to 2$times$ and peak memory usage by over 30% compared to PPO, GRPO, and REBEL.
  arXiv  Detail & Related papers  (2025-05-27T03:58:50Z)
• Submodular Reinforcement Learning [38.40138241424851]
  In reinforcement learning (RL), rewards of states are typically considered additive, and following the Markov assumption, they are $textitindependent$ states visited previously. In many important applications, such as coverage control, experiment design and informative path planning, rewards naturally have diminishing returns, i.e., their value decreases in light of similar states visited previously. We propose $textitsubmodular RL$ (SubRL), a paradigm which seeks to optimize more general, non-additive (and history-dependent) rewards modelled via submodular set functions which capture diminishing returns
  arXiv  Detail & Related papers  (2023-07-25T09:46:02Z)
• Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation [69.0695698566235]
  We study reinforcement learning with linear function approximation and adversarially changing cost functions. We present a computationally efficient policy optimization algorithm for the challenging general setting of unknown dynamics and bandit feedback.
  arXiv  Detail & Related papers  (2023-01-30T17:26:39Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  Inverse reinforcement learning (IRL) aims to recover the reward function and the associated optimal policy. Many algorithms for IRL have an inherently nested structure. We develop a novel single-loop algorithm for IRL that does not compromise reward estimation accuracy.
  arXiv  Detail & Related papers  (2022-10-04T17:13:45Z)
• On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game [140.19656665344917]
  We study the reward-free RL problem, where an agent aims to thoroughly explore the environment without any pre-specified reward function. We tackle this problem under the context of function approximation, leveraging powerful function approximators. We establish the first provably efficient reward-free RL algorithm with kernel and neural function approximators.
  arXiv  Detail & Related papers  (2021-10-19T07:26:33Z)
• Reward-Free Exploration for Reinforcement Learning [82.3300753751066]
  We propose a new "reward-free RL" framework to isolate the challenges of exploration. We give an efficient algorithm that conducts $tildemathcalO(S2Amathrmpoly(H)/epsilon2)$ episodes of exploration. We also give a nearly-matching $Omega(S2AH2/epsilon2)$ lower bound, demonstrating the near-optimality of our algorithm in this setting.
  arXiv  Detail & Related papers  (2020-02-07T14:03:38Z)
• Provably Efficient Exploration in Policy Optimization [117.09887790160406]
  This paper proposes an Optimistic variant of the Proximal Policy Optimization algorithm (OPPO) OPPO achieves $tildeO(sqrtd2 H3 T )$ regret. To the best of our knowledge, OPPO is the first provably efficient policy optimization algorithm that explores.
  arXiv  Detail & Related papers  (2019-12-12T08:40:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.