Source-linked AI summary
Sample Efficient Reinforcement Learning with REINFORCE
Junzi Zhang, Jongho Kim, Brendan O'Donoghue, Stephen Boyd
TL;DR
Prior theory for policy-gradient methods often required exact gradients or diverging mini-batches, limiting its direct relevance to practical REINFORCE. This paper analyzes fixed-batch and single-trajectory REINFORCE with regularization and establishes global-convergence and sample-complexity results.
Problem
Prior policy-gradient theory required exact gradients or state-action visitation estimators with diverging batch sizes, whereas practical REINFORCE uses approximate gradients from single trajectories or fixed-size batches.
Method
The paper combines REINFORCE gradient estimation with soft-max parametrization, progressively reduced regularization, control of bad episodes, and a doubling trick for fixed-size trajectory batches.
Results
˜O(1/ǫ4) sample complexity follows for REINFORCE with a constant regularization parameter and a pre-specified tolerance ǫ.
Takeaways & Limitations
The analysis establishes global convergence rates for practical fixed-batch policy-gradient algorithms and can also support sample-complexity results and other gradient estimators.
Takeaways & Limitations
The analysis assumes a component-wise positive initial distribution and produces bounds that may be far from optimal.
Abstract
from arXiv · showhide
Policy gradient methods are among the most effective methods for large-scale reinforcement learning, and their empirical success has prompted several works that develop the foundation of their global convergence theory. However, prior works have either required exact gradients or state-action visitation measure based mini-batch stochastic gradients with a diverging batch size, which limit their applicability in practical scenarios. In this paper, we consider classical policy gradient methods that compute an approximate gradient with a single trajectory or a fixed size mini-batch of trajectories under soft-max parametrization and log-barrier regularization, along with the widely-used REINFORCE gradient estimation procedure. By controlling the number of "bad" episodes and resorting to the classical doubling trick, we establish an anytime sub-linear high probability regret bound as well as almost sure global convergence of the average regret with an asymptotically sub-linear rate. These provide the first set of global convergence and sample efficiency results for the well-known REINFORCE algorithm and contribute to a better understanding of its performance in practice.
1 Introduction
The paper targets global convergence theory for practical REINFORCE, addressing prior analyses that relied on exact gradients or diverging mini-batch sizes. It develops stronger convergence guarantees for fixed-size or single-trajectory estimates while retaining the widely used algorithm's basic form.
- REINFORCE is a widely used vanilla policy-gradient method because of its empirical performance and implementation simplicity.
- Prior policy-gradient theory was largely restricted to local stationary-point convergence before recent work established global results.
- The paper derives bounds for fixed mini-batches and uses REINFORCE estimators instead of state-action visitation measure-based gradients.
- The analysis provides almost sure and high-probability convergence results, stronger than the expected convergence results dominating vanilla policy-gradient theory.
- The paper establishes the first global convergence results for REINFORCE, including anytime sub-linear high-probability regret and almost sure asymptotically sub-linear average regret.
2 Problem setting and preliminaries
The paper studies episodic reinforcement learning in finite MDPs, optimizing a regularized policy objective through stochastic gradient ascent from sampled trajectories. It organizes learning into phases and evaluates performance using regret.
- Problem setting: The setting is a stationary infinite-horizon discounted finite MDP accessed through successive environment-interaction episodes.
- Problem setting: A policy maps states to action distributions, and the objective is to maximize expected cumulative discounted reward.
- Policy parametrization and surrogate objectives: The method optimizes a regularized surrogate objective whose penalty is progressively reduced toward the original objective.
- Vanilla policy gradient method: Each episode samples a trajectory under the current policy and uses its approximate gradient in a stochastic gradient-ascent update.
- Phased learning: Phased learning fixes regularization within successive phases, applies post-processing between phases, and uses phase-indexed trajectory estimates.
- Performance criteria: Regret measures cumulative policy suboptimality, and its average directly bounds the best iterate's optimality gap.
3 Assumptions and REINFORCE gradients
The analysis assumes soft-max policies with log-barrier regularization and controlled stochastic gradient estimates. REINFORCE estimators use bounded baselines, while trajectory lengths grow logarithmically to control truncation error.
- Assumptions: Assumption 1 uses soft-max policy parametrization together with log-barrier regularization to support the convergence analysis.
- Assumptions: The stochastic gradient estimator must be almost surely bounded, nearly unbiased, and satisfy a bounded second-order moment growth condition.
- Assumptions: Trajectory lengths must grow at least logarithmically with the episode index to control reward loss from truncation.
- Assumptions: The regularized objective is differentiable and strongly smooth under the stated assumptions.
- REINFORCE gradient estimations: REINFORCE gradient estimation subtracts a trajectory-independent baseline from approximate Q-values to potentially reduce estimator variance.
- REINFORCE gradient estimations: A uniformly bounded baseline allows the REINFORCE estimator to satisfy the technical gradient-estimator assumptions.
4 Main convergence results
The paper combines control of bad episodes with adaptive regularization and the doubling trick to obtain high-probability and almost-sure convergence guarantees for REINFORCE.
- Non-convexity and control of “bad” episodes: The gradient threshold defines bad episodes, while episodes outside this set admit a global optimality-gap bound through Proposition 3.The analysis then bounds the number of bad episodes sub-linearly in the phase length.
- Doubling trick: The doubling trick stitches regret bounds from multiple learning phases and removes dependence on a pre-specified tolerance.The regularization parameter is adapted across phases.
- From high probability to almost sure convergence: An anytime sub-linear high-probability regret bound implies almost-sure convergence of average regret through a logarithmic-dependency lemma.The implication is stated for bounds of the form given in equation (11).
- Single phase analysis: For fixed tolerance ǫ, the average regret converges to a constant multiple of ǫ at a sub-linear rate.The single-phase bound includes a sub-linear regret term and a tolerance-dependent error term.
- Overall regret bound: The resulting finite-mini-batch analysis removes the non-vanishing Θ(1/M^p) term present in earlier results and yields the first sub-linear regret bound in this setting.Earlier results required exact deterministic updates or retained a mini-batch-size error term.
5 Extension to mini-batch updates
The mini-batch extension samples M independent trajectories per update, modifies regret to account for shared iterates, and establishes high-probability and almost-sure guarantees.
- Mini-batch updates: Each inner iteration samples M ≥1 independent trajectories and computes one approximate gradient from the resulting trajectory-specific estimates.The update is modified accordingly; the formal algorithm appears in Appendix D.
- Regret with mini-batches: The mini-batch regret definition assigns the same contribution to all episodes sharing an iterate and separately accounts for remaining episodes in a partial iteration.This handles episode counts not divisible by M.
- Regret with mini-batches: Corollary 7 establishes a joint high-probability regret bound for all episodes under the mini-batch algorithm.The result is stated under the assumptions of Lemma 12 and the specified phase schedule.
- Regret with mini-batches: The mini-batch guarantees also imply almost-sure convergence, with a trade-off between M^1/6 and M^-5/6 terms.The trade-off reflects lower variance for larger batches versus more frequent updates for smaller batches.
6 Conclusion and open problems
The paper presents global convergence and sample-complexity results for practical REINFORCE updates, while identifying extensions and unresolved limitations.
- Conclusion: The work establishes global convergence rates for practical policy-gradient algorithms using fixed-size trajectory mini-batches and REINFORCE estimation.The contribution is framed around practical fixed-size sampling rather than diverging batch sizes.
- Conclusion: The general results can also apply to actor-critic and state-action visitation-measure estimators when the required constants are verified.The REINFORCE-specific instantiations are supplemented by a broader appendix theorem.
- Conclusion: The analysis implies a ˜O(1/ǫ4) sample-complexity bound for Algorithm 1 with REINFORCE and constant regularization.The result applies for any pre-specified tolerance ǫ, with logarithmic factors suppressed.
- Extensions: The results are discussed for the stationary infinite-horizon discounted setting, with finite-horizon non-stationary extensions described as straightforward.The finite-horizon parametrization has dimension SAH, and regret can be expressed using total time steps T ≤HN.
- Open problems: Open problems include removing the positive initial-distribution assumption, sharpening the bounds, and analyzing entropy regularization with stochastic estimates.The paper states that the current bounds are likely far from optimal and leaves the stochastic entropy-regularization question unresolved.
A.1 Proof of Lemma 2 (with b = 0)
The appendix verifies the boundedness, variance, and near-unbiasedness conditions needed for the REINFORCE gradient estimator under the stated assumptions.
- Proof of Lemma 2: With no baseline, the proof first validates the assumptions governing REINFORCE gradient estimation.The proof explicitly restricts this presentation to b = 0.
- Gradient estimation boundedness: Bounded rewards and soft-max parametrization control the return and score-function terms used in the gradient estimator.The return is bounded by 1/(1−γ), while the score-function norm is at most 2.
- Validation of nearly unbiasedness: The near-unbiasedness verification uses the policy-transition sampling relation together with Cauchy inequality and earlier bounds.The cited theorem supplies the policy-gradient relation used in this step.
- Validation of bounded second-order moment growth: The proof defines a uniform variance bound ¯V for the policy-gradient vector and uses it to bound the conditional second-order moment.The resulting constants can be taken as M2 = 2 and M1 = 32/(1−γ)^4 + ¯V.
A.2 Proof of Lemma 2
The proof bounds the variance-related quantity for the REINFORCE gradient estimator by expressing it through sampled trajectories and applying auxiliary inequalities.
- The proof follows the b = 0 case closely, with differences highlighted for the current setting.
- The trajectory τ is sampled from the MDP under policy πθ, and the estimator uses the trajectory return estimate ˆQ(st, at).
- M1 = 32/(1 −γ)4 + ¯Vb and M2 = 2 are used in the variance-bound construction.
- The resulting quantity ¯Vb is bounded analogously to ¯V in the b = 0 proof.
- An elementary monotonicity argument supplies the logarithmic inequalities used repeatedly in the proof.
B.1 Proof of Lemma 4
The proof applies the Borel-Cantelli lemma to show that the relevant bad events occur only finitely often, yielding the desired almost-sure conclusion.
- The proof sets δN = 1/N^2 and defines a sequence of events for the almost-sure argument.
- Prob( ¯AN occurs infinitely often) = 0, so the complement event holds eventually with probability one.
- Because the complement of ¯AN is contained in AN, the proof concludes the required result.
B.2 Proof of Theorem 5
The proof first controls weighted gradient norms within each phase, then converts that control into a phase-regret bound using martingale concentration and smoothness arguments.
- Theorem 9 gives a high-probability bound for every K in a phase under the prescribed step-size choice.
- The proof separates into bounding the weighted gradient-norm sum and then bounding phase regret from that estimate.
- Conditional independence of each sampled trajectory from previous policies and trajectories supports the filtration-based martingale analysis.
- Azuma-Hoeffding concentration controls the martingale fluctuations uniformly over the phase iterations.
- Summing the per-iteration inequalities yields the phase-level regret estimate, using R(θ) ≤ 0 for all θ ∈ Θ.
- The phase-regret argument handles indices with and without sufficiently large gradient terms before applying the uniform probability bound.
B.3 Overall regret bound for general policy gradient estimators
The general regret analysis extends the REINFORCE result to policy-gradient estimators under stated assumptions. With doubling phase lengths and shrinking regularization, it establishes an anytime high-probability bound and almost-sure convergence.
- Theorem 10 generalizes the REINFORCE regret result to general policy-gradient estimators.
- The analysis uses doubling phase lengths Tl = 2^lT0 and a phase-dependent choice ϵl = T_l^-1/6.
- With probability at least 1 −δ, the overall regret bound holds for every N ≥ 0.
- The average regret converges almost surely to zero at asymptotic rate O(N^-1/6(log N)5/2).
- The high-probability analysis allocates failure probabilities across phases and combines phase bounds through the doubling schedule.
- The specialized REINFORCE corollary makes problem-dependent quantities explicit under its estimator and hyperparameter assumptions.
D Mini-batch phased policy gradient method
The mini-batch phased policy-gradient method processes batches of trajectory-based gradient estimates within phases, using regularization, post-processing, and scheduled step sizes. Its formal analysis establishes high-probability guarantees under stated assumptions.
- Gradient estimation: The mini-batch gradient estimator averages independent trajectory estimates, inheriting a variance bound from the single-trajectory analysis.The variance argument relies on the variance of sums of independent random variables and uses the same constants as Lemma 2.
- Phased schedule: The method proceeds through phases with scheduled step sizes, phase lengths T_l = 2^l, regularization parameters, and post-processing tolerance.The formal corollary sets T_l = 2^l and epsilon_l = 2^-l/6, alongside specified step-size and post-processing choices.
- Guarantees: The formal result applies for any confidence level delta in (0, 1) and any N >= M >= 1 under the stated assumptions.The guarantee is asserted with probability at least 1 - delta for the mini-batch Algorithm 4.
- Algorithm structure: Algorithm 4 uses a fixed batch size M and computes approximate gradients from M trajectories generated under the current policy.The algorithm specifies batch size M as an input and forms trajectory-based gradient estimates before averaging them.