Sample Efficient Reinforcement Learning with REINFORCE

• REINFORCE is a widely used vanilla policy-gradient method because of its empirical performance and implementation simplicity.Source: §1 · p. 1
• Prior policy-gradient theory was largely restricted to local stationary-point convergence before recent work established global results.Source: §1 · p. 1
• The paper derives bounds for fixed mini-batches and uses REINFORCE estimators instead of state-action visitation measure-based gradients.Source: §1 · p. 1
• The analysis provides almost sure and high-probability convergence results, stronger than the expected convergence results dominating vanilla policy-gradient theory.Source: §1 · p. 2
• 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.Source: §1.1 · p. 2

Problem setting

• The setting is a stationary infinite-horizon discounted finite MDP accessed through successive environment-interaction episodes.Source: §2 · p. 2, §2.1 · p. 2, §2.2 · p. 2
• A policy maps states to action distributions, and the objective is to maximize expected cumulative discounted reward.Source: §2.1 · p. 2

Policy parametrization and surrogate objectives

• The method optimizes a regularized surrogate objective whose penalty is progressively reduced toward the original objective.Source: §2.2 · p. 2

Vanilla policy gradient method

• Each episode samples a trajectory under the current policy and uses its approximate gradient in a stochastic gradient-ascent update.Source: §2.2 · p. 3

Phased learning

• Phased learning fixes regularization within successive phases, applies post-processing between phases, and uses phase-indexed trajectory estimates.Source: §2.3 · p. 3

Performance criteria

• Regret measures cumulative policy suboptimality, and its average directly bounds the best iterate's optimality gap.Source: §2.3 · pp. 3–4

Assumptions

• Assumption 1 uses soft-max policy parametrization together with log-barrier regularization to support the convergence analysis.Source: §3.1 · p. 4
• The stochastic gradient estimator must be almost surely bounded, nearly unbiased, and satisfy a bounded second-order moment growth condition.Source: §3.1 · p. 4
• Trajectory lengths must grow at least logarithmically with the episode index to control reward loss from truncation.Source: §3.1 · p. 4
• The regularized objective is differentiable and strongly smooth under the stated assumptions.Source: §3.1 · p. 4

REINFORCE gradient estimations

• REINFORCE gradient estimation subtracts a trajectory-independent baseline from approximate Q-values to potentially reduce estimator variance.Source: §3.2 · pp. 4–5
• A uniformly bounded baseline allows the REINFORCE estimator to satisfy the technical gradient-estimator assumptions.Source: §3.2 · p. 5

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.Source: §4.1 · p. 5

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.Source: §4.1 · p. 5, §4.2 · pp. 5–6

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).Source: §4.1 · p. 5, §4.2 · p. 6

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.Source: §4.2 · p. 6

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.Source: §4.2 · p. 6

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.Source: §5 · p. 6

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.Source: §5 · pp. 6–7
• 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.Source: §5 · p. 7
• 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.Source: §5 · p. 7

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.Source: §6 · p. 7
• 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.Source: §6 · p. 7
• 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.Source: §6 · p. 7

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.Source: §6 · p. 7

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.Source: §6 · p. 7

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.Source: §A.1 · p. 11

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.Source: §A.1 · p. 11

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.Source: §A.1 · pp. 11–12

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.Source: §A.1 · p. 13

• The proof follows the b = 0 case closely, with differences highlighted for the current setting.Source: §A.2 · p. 13
• The trajectory τ is sampled from the MDP under policy πθ, and the estimator uses the trajectory return estimate ˆQ(st, at).Source: §A.2 · p. 14
• M1 = 32/(1 −γ)4 + ¯Vb and M2 = 2 are used in the variance-bound construction.Source: §A.2 · p. 14
• The resulting quantity ¯Vb is bounded analogously to ¯V in the b = 0 proof.Source: §A.2 · p. 14
• An elementary monotonicity argument supplies the logarithmic inequalities used repeatedly in the proof.Source: B Proofs for convergence analysis · p. 14

• The proof sets δN = 1/N^2 and defines a sequence of events for the almost-sure argument.Source: §B.1 · p. 14
• Prob( ¯AN occurs infinitely often) = 0, so the complement event holds eventually with probability one.Source: §B.1 · p. 14
• Because the complement of ¯AN is contained in AN, the proof concludes the required result.Source: §B.1 · p. 14

• Theorem 9 gives a high-probability bound for every K in a phase under the prescribed step-size choice.Source: §B.2 · p. 15
• The proof separates into bounding the weighted gradient-norm sum and then bounding phase regret from that estimate.Source: §B.2 · p. 15
• Conditional independence of each sampled trajectory from previous policies and trajectories supports the filtration-based martingale analysis.Source: §B.2 · pp. 15–16
• Azuma-Hoeffding concentration controls the martingale fluctuations uniformly over the phase iterations.Source: §B.2 · p. 16
• Summing the per-iteration inequalities yields the phase-level regret estimate, using R(θ) ≤ 0 for all θ ∈ Θ.Source: §B.2 · p. 16
• The phase-regret argument handles indices with and without sufficiently large gradient terms before applying the uniform probability bound.Source: §B.2 · pp. 16–17

• Theorem 10 generalizes the REINFORCE regret result to general policy-gradient estimators.Source: §B.3 · p. 17
• The analysis uses doubling phase lengths Tl = 2^lT0 and a phase-dependent choice ϵl = T_l^-1/6.Source: §B.3 · p. 17
• With probability at least 1 −δ, the overall regret bound holds for every N ≥ 0.Source: §B.3 · p. 17
• The average regret converges almost surely to zero at asymptotic rate O(N^-1/6(log N)5/2).Source: §B.3 · pp. 18–19
• The high-probability analysis allocates failure probabilities across phases and combines phase bounds through the doubling schedule.Source: §B.3 · pp. 18–19
• The specialized REINFORCE corollary makes problem-dependent quantities explicit under its estimator and hyperparameter assumptions.Source: C Formal statement of REINFORCE regret… · pp. 19–20

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.Source: D Mini-batch phased policy gradient… · p. 20

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.Source: D Mini-batch phased policy gradient… · p. 20

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.Source: D Mini-batch phased policy gradient… · p. 20

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.Source: D Mini-batch phased policy gradient… · pp. 20–21