Towards Optimal Policy Improvement

Yaniv Oren; Viliam Vadocz; Wiktor Zabka; Thomas Evers; Jan Robine; Wendelin Böhmer; Matthijs T. J. Spaan; Martha White

cs.LGOct 1, 2026

Towards Optimal Policy Improvement

Authors: Yaniv Oren, Viliam Vadocz, Wiktor Zabka, Thomas Evers, Jan Robine, Wendelin Böhmer, Matthijs T. J. Spaan, Martha White, +2 more

Organizations: Department of Intelligent Systems, TU Delft · Centrum Wiskunde & Informatica, Amsterdam · Department of Computer Science, ETH Zürich · Department of Computing Science, University of Alberta · Information Systems, TU Eindhoven · Delft Institute of Applied Mathematics, TU Delft

Abstract

Practical Reinforcement Learning (RL) algorithms learn to solve Markov Decision Processes (MDPs) through iterative policy improvement in the presence of approximate evaluation. We study policy improvement from first principles, defining optimal policy improvement as producing the best policy attainable in a single update under specified constraints. We show that optimal improvement restricted to a set of states is equivalent to solving an induced MDP, characterizing planning with an explicit or implicit model as a path towards optimal policy improvement. Because practical methods commonly solve such induced problems through iterative improvement in the form of greedification, we take steps towards optimal greedification under the central practical constraint of approximate evaluation. We formulate greedification under this constraint as probabilistic decision-making under uncertainty and derive a novel operator that is optimal with respect to the resulting objective. Empirically, the operator and its practical gradient-based approximations improve aggregate performance across GumbelAlphaZero, SAC, ReBRAC and Generalized Policy Iteration, in experiments spanning discrete and continuous actions, model-based and model-free, online and offline RL.

Figures & tables

Figure 1: Noised policy iteration: normalised

V^{\pi}(s_{0})

at iteration

40

over

20

grid environments, 95% Gaussian CI. Model-based, discrete: Bayes Elo at

34

M training frames, mean, min. and max. over

5

training seeds in 9x9 Go. Model-free, continuous: mean normalised returns at

1

M steps on

10

DeepMind Control Suite tasks, mean and 95% Gaussian CI. Offline: normalised return at

1

M steps on

4

D4RL medium-replay tasks, mean and 95% Gaussian CI.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2: Policy Iteration experiments with different policy improvement operators and uncertain evaluation, mean and 95% Gaussian CI. Left: Example learning curves. Center: Sample-efficiency vs. starting noise magnitude, measured as Area Under the Curve (AUC) of learning curves until 100 iterations (higher is better). Right: AUC vs. hyperparameter combination. The performance landscape exhibits a single broad ridge of high performance, with performance degrading smoothly away from the ridge.

Figure 3: Policy Iteration with a 1-step Bellman update ( $k=1$ ), otherwise identical to Figure 2 .

Figure 4: Playing strength in training on

9\times 9

Go with

M=64

. Every checkpoint of every agent and every seed plays every other resulting in a single set of Elo scores. Bold curves are the mean over 5 training seeds per agent. Faint curves are the seeds themselves, with

95\%

BayesElo CI.

Figure 5: Playing strength per agent with the same set of DNNs. Bayes elo and 95% CIs.

Figure 6: Left: Variance based on one-step TD residual proxies for evaluation error on different opening-book positions under one network on

9\times 9

Go with 95% percentile bootstrap over positions. Right: the shape of the

Q_{\phi}

residual, on a log density scale. In grey the raw pooled residual, a scale mixture over actions of differing

\sigma

. In blue is the same data centered and scaled per position; dashed is the fitted

\mathcal{N}(0,1)

Figure 7: Per-environment learning curves on the 10 DeepMind Control Suite tasks, showing unnormalised episodic return against environment steps. Mean across 10 seeds and

95\%

interval.

Dataset	per-dataset $\tau^{2},\beta$	single pair $\tau^{2}=2$ , $\beta=0.5$	ReBRAC
	ReBRAC $+\,\mathcal{I}_{\text{opt}}$
halfcheetah-medium-replay	$\mathbf{50.86\pm 1.09}$	$\mathbf{50.30\pm 1.43}$	$49.65\pm 0.28$
hopper-medium-replay	$\mathbf{87.00\pm 8.80}$	$\mathbf{87.00\pm 8.80}$	$\mathbf{88.24\pm 6.80}$
walker2d-medium-replay	$\mathbf{84.69\pm 3.19}$	$\mathbf{84.69\pm 3.19}$	$78.75\pm 3.91$
ant-medium-replay	$\mathbf{40.17\pm 7.89}$	$\mathbf{40.17\pm 7.89}$	$17.09\pm 3.05$

Appendix

Table 1: Per-environment offline RL results on the four D4RL medium-replay datasets. Entries are the D4RL score of the final policy evaluated over

56

episodes, mean and

95\%

Gaussian CI over

20

runs per arm per environment (

10

for the single-pair setting on halfcheetah). Bold marks the highest mean in each row together with every entry that is not significantly worse than it, at

p<0.05

under a two-sided Welch

t

-test over runs ( Welch, 1947 ) ; several bold entries in a row therefore indicate a tie.

Experiment	Number of Seeds per Agent
Policy iteration	$100$ seeds $\times$ $20$ environments
Model-based, discrete	$5$ training seeds
Model-free, continuous	$10$ seeds $\times$ $10$ environments
Offline	$20$ seeds $\times$ $4$ environments

Appendix

Table 2: Number of seeds included in each experiment.

Component	Parameter	Value
$\mathcal{I}_{\text{opt}}$	Advantage prior variance ( $\tau^{2}$ )	$(0.17)^{2}$
	KL regularization strength ( $\beta$ )	$0.07$
$\mathcal{I}_{\text{reg}}$	Temperature ( $\eta$ )	$4.89$
Environments	Grid size ( $\|\mathcal{S}\|\times\|\mathcal{A}\|$ )	$25\times 5$
Noise schedule	Initial noise bound ( $a_{0}$ )	$50$
(Eq. 135 )	Decay ( $\gamma_{\text{dec}}$ )	$0.998$

Appendix

Table 3: Hyperparameters for the Policy Iteration experiments.

Component	Parameter	Value
$\mathcal{I}_{\text{opt}}$	Advantage prior variance ( $\tau^{2}$ )	$0.08$
	KL regularization strength ( $\beta$ )	$0.01$
$\mathcal{I}_{reg}$ (GumbelMCTS)	$c_{visit}$	$50$
	$c_{scale}$	$1.0$
PUCT (AlphaZero)	$c_{\text{init}}$	$1.25$
	$c_{\text{base}}$	$19652$

Appendix

Table 4: Hyperparameters for the discrete-action model-based GAZ experiments.

Component	Parameter	Value
$\mathcal{I}_{\text{opt}}$	Advantage prior variance ( $\tau^{2}$ )	$0.4$
	Num. actions sampled for $V_{\phi_{i}}(s)$	$32$
SAC	Optimizer	Adam
	Actor learning rate	$3\cdot 10^{-4}$
	Critic and entropy learning rate	$10^{-3}$
	Batch size	$256$

Appendix

Table 5: Hyperparameters for the online classical continuous control SAC experiments

Component	Parameter	Value
$\mathcal{I}_{\text{opt}}$	Advantage prior variance ( $\tau^{2}$ ), halfcheetah-medium-replay	$8$
	Advantage prior variance ( $\tau^{2}$ ), hopper-medium-replay	$2$
	Advantage prior variance ( $\tau^{2}$ ), walker2d-medium-replay	$2$
	Advantage prior variance ( $\tau^{2}$ ), ant-medium-replay	$2$
	KL regularization strength ( $\beta$ ), all datasets	$0.5$
ReBRAC	Critics ( num_critics )	$2$

Appendix

Table 6: Hyperparameters for the offline RL ReBRAC experiments.

Explore similar work

Mathematical methods of reinforcement learning
Jul 8, 2026Denis Belomestny, Alexander Gasnikov, Egor Gladin +5Markov Decision Processes Stochastic Approximation
Duisburg-Essen University, HSE University · Innopolis University, MIPT, HSE University · HSE University +1
Relating Reinforcement Learning to Dynamic Programming-Based Planning
Mar 8, 2026Filip V. Georgiev, Kalle G. Timperi, Başak Sakçak +1Offline Reinforcement Learning Sequential Decision Making
Center for Applied Computing, Faculty of Information Technology and Electrical Engineering, University of Oulu, Finland · Dept. of Advanced Computing Sciences, Maastricht University, the Netherlands
Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimality
May 23, 2026Amogh Palasamudram, Jakub Svoboda, Suguman Bansal +1Reachability Convergence
Georgia Institute of Technology, USA · Institute of Science and Technology, Austria · Dartmouth College, USA

Jul 8, 2026, math.OCJ/K move · Enter open · S save

Mathematical methods of reinforcement learning

Denis Belomestny, Alexander Gasnikov, Egor Gladin, Alexey Naumov+4

Duisburg-Essen University, HSE University · Innopolis University, MIPT, HSE University · HSE University+1

Markov Decision Processes Stochastic Approximation Mathematics Prompt Optimization

Open paper AskPDF arXiv

Reinforcement learning (RL) is increasingly grounded in tools from probability, optimization, and operator theory. This survey organizes the mathematical structures that underpin the design and analysis of modern algorithms in RL. We begin from Markov decision processes (MDPs) and the Bellman operators, emphasizing contraction mappings, monotonicity, and fixed-point theory that yield convergence guarantees and rates for value and policy iteration, and temporal-difference schemes. We then develop the optimization perspective: stochastic approximation and martingale methods, convex duality and the role of regularization linking mirror/proximal methods. Function approximation is treated through linear and non-linear settings, covering stabilization, error decomposition, and sample-complexity via concentration inequalities for dependent data and mixing processes. We further cover off-policy evaluation/learning, constrained RL and constrained MDPs (CMDPs). Throughout we unify algorithmic templates under common operator and variational lenses, highlighting both finite-sample bounds and asymptotic results. Our presentation is intended to provide a unified mathematical entry point for researchers in probability, optimization, and statistics interested in reinforcement learning.

Abstract

Explore similar work

Mathematical methods of reinforcement learning

Relating Reinforcement Learning to Dynamic Programming-Based Planning

Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimality