Source-linked AI summary
f-Divergence constrained policy improvement
Boris Belousov, Jan Peters
TL;DR
KL-constrained policy improvement helps limit large steps toward unknown state-space regions, and this paper extends the approach to generic f-divergences. Its framework connects divergence-dependent policy updates with compatible policy evaluation, including soft-max under KL and log-sum-exp evaluation.
Problem
Many reinforcement-learning algorithms constrain successive policies with KL divergence to avoid large steps toward unknown state-space regions.
Source: §1 · p. 1Method
The paper develops policy-improvement rules that constrain policy change with f-divergences and use convex-conjugate properties in the derivations.
Source: §2 · p. 3, §5 · p. 15Results
The framework connects α-dependent policy updates to evaluation rules: KL yields soft-max with log-sum-exp evaluation, while α = 2 yields an update compatible with evaluation closely related to mean squared Bellman error.
Source: §5 · p. 16Takeaways & Limitations
Choosing the divergence determines both the policy-improvement step and its compatible policy-evaluation step.
Source: §5 · p. 16When 0 is outside dom f′, an improved policy cannot assign zero probability to actions that had positive probability under the old policy.
Source: §3.1 · p. 5
Abstract
from arXiv · showhide
To ensure stability of learning, state-of-the-art generalized policy iteration algorithms augment the policy improvement step with a trust region constraint bounding the information loss. The size of the trust region is commonly determined by the Kullback-Leibler (KL) divergence, which not only captures the notion of distance well but also yields closed-form solutions. In this paper, we consider a more general class of f-divergences and derive the corresponding policy update rules. The generic solution is expressed through the derivative of the convex conjugate function to f and includes the KL solution as a special case. Within the class of f-divergences, we further focus on a one-parameter family of $\alpha$-divergences to study effects of the choice of divergence on policy improvement. Previously known as well as new policy updates emerge for different values of $\alpha$. We show that every type of policy update comes with a compatible policy evaluation resulting from the chosen f-divergence. Interestingly, the mean-squared Bellman error minimization is closely related to policy evaluation with the Pearson $\chi^2$-divergence penalty, while the KL divergence results in the soft-max policy update and a log-sum-exp critic. We carry out asymptotic analysis of the solutions for different values of $\alpha$ and demonstrate the effects of using different divergence functions on a multi-armed bandit problem and on common standard reinforcement learning problems.
1. Introduction
Many reinforcement-learning methods constrain successive policies with KL divergence to avoid large steps toward unknown state-space regions. This paper extends that policy-improvement perspective to generic f-divergences, presenting it as a way to unify existing algorithms and develop alternatives.
1. Introduction
- KL constraints limit large policy steps toward unknown regions of the state space in several established reinforcement-learning algorithms.These approaches can also be viewed as free-energy minimization.Source: §1 · p. 1
- The paper explores using generic f-divergences instead of KL divergence to constrain policy improvement.The resulting objective resembles the free-energy objective.Source: §1 · p. 1
- The f-divergence perspective unifies existing algorithms and may support algorithms better suited to particular problems.The authors describe their work as, to their knowledge, the first to examine reinforcement-learning policy improvement from this perspective.Source: §1 · p. 2
2. Background
The section introduces f-divergences and the α-divergence family, then presents convex-conjugate properties used in the paper’s derivations.
2. Background
- An f-divergence generalizes similarity measures between distributions and uses a convex function f with f(1) = 0.The paper assumes f is continuously differentiable and that π is absolutely continuous with respect to q.Source: §2 · p. 2
- The derivations use unnormalized distributions and impose normalization as a constraint afterward.The paper states that this formulation benefits its derivations.Source: §2 · p. 2
- The α-divergence is a one-parameter family that includes KL, reverse KL, Hellinger, Pearson χ2, and Neyman χ2 divergences.The familiar divergences lie on the parabola y = α(α −1), with reverse divergences symmetric around α = 0.5.Source: §2 · pp. 2–3
- The convex-conjugate derivative satisfies (f*)′ = (f′)−1, a property used in the paper’s derivations.Table 1 lists common fα functions, their convex conjugates, and derivatives.Source: §2 · p. 3, Table 1 · p. 3
3. Policy improvement with f-divergence for multi-armed bandits
The section formulates policy improvement as maximizing estimated return while regularizing policy change with an f-divergence, then examines how α and temperature shape updates and regret. In bandits, α∈[0,2] performs comparably with UCB after around 400 steps, while the best α depends on the time horizon.
3. Policy improvement with f-divergence for multi-armed bandits
- The bandit setting makes the exploration–exploitation effects of entropic penalties easier to inspect and serves as a foundation for the reinforcement-learning section.The resulting algorithm is closely related to Exp3, which performs well on adversarial but lags state-of-the-art methods on stochastic bandits.Source: §3 · pp. 3–4
- The bandit update maximizes estimated expected return while penalizing change from the old policy with an f-divergence weighted by temperature η.This formalizes the exploration–exploitation trade-off as a convex optimization problem; the penalty formulation generalizes to related constraint formulations.Source: §3.1 · p. 4, §3 · p. 4
3.2 Effects of the exploration-exploitation-tradeoff and the divergence type
- When α>1, the update may assign zero probability to actions, so non-negativity constraints and their Lagrange multipliers can matter; for α≤1, the multipliers vanish.If the old policy assigns positive probability to every action, sufficiently high temperature makes the constraints inactive.Source: §3.1 · p. 5, §3.2 · p. 6
- Temperature η controls the magnitude of policy change: as η→0 the update becomes greedy, while as η→∞ it returns to the old policy.For intermediate η, the policy lies between focusing on the best action and staying close to the old policy; α affects the search direction.Source: §3.2 · pp. 5–6
- α selects among different policy forms: α→−∞ recovers ϵ-greedy, α=1 gives soft-max, α=2 gives a linear policy, and large positive α gives ϵ-elimination.For α≤1, policies are ϵ-soft; for α>1, some actions may receive zero probability. The α=1 soft-max has a log-sum-exp baseline, and α=2 has a linear advantage-reweighted form when constraints are inactive.Source: §3.2 · pp. 6–7
- For α<1, the optimal baseline lies between the old policy’s expected return and the maximum action value; for α>1, it lies between the minimum action value and the old policy’s expected return.As temperature increases, the baseline shifts toward the old policy’s expected return.Source: §3.2 · p. 7, Table 3 · p. 7
3.3 Empirical evaluation of policy improvement with f-divergence in bandits
- In the 10-armed bandit, α<1 policies are peaked and heavy-tailed and converge faster late in learning, whereas α≥1 policies are more uniform and may linger between two best actions.At fixed η=2, α<1 policies retain small probability for low-value actions; α≥1 policies can assign them zero mass.Source: §3.3 · p. 7, Figure 3 · p. 8
- α∈[0,2] performs comparably with UCB after around 400 steps; small α values achieve the best regret, and the minimizing α shifts with the time horizon.Extreme α values accumulate more regret; large negative values can prematurely converge to a suboptimal action, while large positive values can eliminate the best action or prolong final selection.Source: Figure 2 · p. 7, §3.3 · pp. 8–9, Figure 4 · p. 8
4. Policy iteration with state-action f-divergence for ergodic MDPs
The section formulates policy iteration with a state-action f-divergence constraint, pairing dual policy evaluation with an analytic policy update. It relates special divergence choices to squared-error objectives and shows that α affects learning dynamics across grid-world environments.
4. Policy iteration with state-action f-divergence for ergodic MDPs
- The f-divergence policy-iteration scheme evaluates a policy by solving a convex dual problem, then improves it with the analytic solution to the primal problem.The state-action distribution under the new policy is constrained to remain similar to that under the old policy while seeking higher expected return.Source: §4.1 · pp. 9–10
4.2 Two important special cases: α = 1 and α = 2
- For Pearson χ² (α = 2), policy evaluation minimizes squared differential advantage and policy improvement linearly reweights the old policy; at high temperatures, any f-divergence approaches this solution.The Pearson χ² solution is a first-order approximation of the KL solution at high temperature.Source: §4.2 · p. 11
4.3 Practical algorithm: sample-based policy iteration with f-divergence
- The practical algorithm replaces environment expectations with sample averages, supports linear value-function approximation through a steady-features constraint, and uses a decaying temperature parameter.The authors also describe omitting κ variables under specified α or temperature conditions and adding slack to the convex-conjugate domain constraint for robustness.Source: §4.3 · p. 12
4.5 Relation to the mean squared Bellman error minimization
- Pearson χ²-penalized policy evaluation is equivalent to minimizing mean squared differential advantage, which lies between TD-error and Bellman-error minimization.The dual objective tends to the MSDA objective as temperature increases, making its SGD a continuous generalization of residual-gradient learning to finite temperatures.Source: §4.5 · pp. 13, 15
4.4 Empirical results on ergodic MDPs
- Moderate α values (0–1) offer the strongest balance in the grid-world experiments, while α < 0 can improve faster initially and α > 1 can be unstable or fail to reach the optimum.The Hellinger distance (α = 0.5) outperformed reverse KL (α = 0) and KL (α = 1) on FrozenLake.Source: §4.4 · pp. 12–13, Figure 5 · p. 14
5. Conclusion
The framework derives policy-improvement and policy-iteration algorithms by constraining policy change with f-divergences. The divergence choice shapes both exploration and, in average-reward reinforcement learning, the compatible policy evaluation.
5. Conclusion
- Different α-divergences correspond to different exploration strategies, and the optimal α depends on the time horizon.Source: §5 · p. 15
- The soft-max policy update used by Exp3 and the gradient bandit algorithm is the KL-divergence special case.Source: §5 · p. 16
- The choice of f-divergence determines both the policy-improvement step and its compatible policy evaluation in average-reward reinforcement learning.The framework also provides an efficient sample-based solution for this setting.Source: §5 · p. 16
Appendix A.
Appendix A reports experimental settings, including temperature schedules and per-environment tables for Chain, CliffWalking, and FrozenLake.
Appendix A.
- The temperature parameter η is exponentially decayed across policy-iteration steps.Its initial value and decay factor depend on reward scale and the number of samples per policy update.Source: Appendix A · p. 17
- The environment tables list temperature parameters, samples per policy update, policy-iteration steps, and runs used for averaging.They also include environment-specific settings where applicable.Source: Appendix A · p. 17
- The appendix includes environment tables for Chain, CliffWalking, and FrozenLake.Source: Table 4 · p. 17, Table 5 · p. 17, Table 6 · p. 17