Reinforcement Learning in MDPs with Information-Ordered Policies

Zhongjun Zhang; Shipra Agrawal; Ilan Lobel; Sean R. Sinclair; Christina Lee Yu

stat.MLAug 5, 2025

Reinforcement Learning in MDPs with Information-Ordered Policies

Authors: Zhongjun Zhang, Shipra Agrawal, Ilan Lobel, Sean R. Sinclair, Christina Lee Yu

Organizations: Department of Industrial Engineering and Management Sciences, Northwestern University · Department of Industrial Engineering and Operations Research, Columbia University · Technology, Operations, and Statistics, Stern School of Business, New York University · School of Operations Research and Information Engineering, Cornell University

Abstract

Many operational Markov decision processes provide structured information where a trajectory generated under one policy may also reveal how other policies would have performed. We formalize this through an information order over a parameterized policy class, writing $π_{θ'} \preceq π_θ$ when data collected under $π_θ$ can be used to estimate the long-run average cost of $π_{θ'}$ . We develop an epoch-based reinforcement learning algorithm for infinite-horizon average-cost MDPs with continuous state and action spaces that exploits this order through counterfactual inference. For a $d$ -dimensional policy class whose information order has width $w$ , the algorithm achieves $\widetilde O(H\sqrt{wdT/α})$ regret relative to the optimal policy in the class, where $H$ is a bias span upper bound and $α$ denotes an "information ratio". Thus, the width captures the effective exploration complexity of the problem, interpolating between full counterfactual feedback and unstructured policy learning. We instantiate the framework in lost-sales inventory systems with positive lead times, dual-sourcing systems governed by dual-index policies, and queues with state-dependent service rates. These applications yield new regret guarantees without requiring global convexity of the average-cost function or specialized arrival-rate structure. Numerical experiments show that exploiting the information order substantially improves learning performance over existing general-purpose and problem-specific benchmarks.

Figures & tables

Distribution	Algorithm	Inventory Control		Dual Sourcing		Queuing
		Small	Large	Small	Large	Large
Exponential	Optimal $(g_{\theta^{*}})$	$2.5$	$39.1$	$1.9$	$20.3$	$9.5$
	ERM ( Sinclair et al. 2023b )	$2.6(2\%)$	$39.2(0\%)$	$1.9(1\%)$	$20.3(0\%)$	$9.6(1\%)$
	I OPEA	${}^{\star}2.6(3\%)$	$40.1(2\%)$	${}^{\star}2.0(5\%)$	${}^{\star}26.0(28\%)$	${}^{\star}10.5(11\%)$
	PPO ( Schulman et al. 2017 )	$3.8(49\%)$	${}^{\circ}132.4(238\%)$	$2.9(53\%)$	${}^{\circ}112.0(451\%)$	${}^{\star}9.8(3\%)$
	SGD	${}^{\star}2.6(3\%)$	${}^{\circ}43.0(10\%)$	${}^{\star}2.1(10\%)$	${}^{\circ}55.2(172\%)$	–

Table 1: Average cost of the learned policy at the timestep

g_{\theta_{T}}

for

T=10^{5}

(small-scale) and

T=3\times 10^{5}

(large-scale) achieved by each algorithm, under three demand distributions. The queuing case study is estimated at

T=3\times 10^{5}

\star

indicates a significant improvement and

\circ

a significant decrease over P roblem-Specific by Welch’s

t

-test with

p<0.05

. In parentheses we report relative performance

(g_{\theta_{T}}-g_{\theta^{*}})/g_{\theta^{*}}

. F eedback Graph is omitted in large-scale due to compute constraints. The performance of SGD is omitted in the queuing models as it is essentially equivalent to PPO . See Table 4 for hyperparameters.

Figure 1: Comparison of the long‐run average cost

g_{\theta}

over time

T

for different algorithms in the small‐scale dual‐sourcing problem up to

T=10^{6}

. We assume the demand follows the normal distribution as in Table 4 . For F eedback Graph ( Dann et al. 2020 ) , data are shown only to

T=10^{5}

. I OPEA attains near‐optimal gain by

T=10^{4}

; B ASA ( Chen and Shi 2025 ) remains suboptimal and continues to decline even at

T=10^{6}

; F eedback Graph matches B ASA’s long‐run cost at

T=10^{5}

but with much larger variance; P PO converges markedly slower than all other methods. SGD fails to converge effectively, as the problem is non-convex. Note that in some trials P PO and F eedback Graph may exceed the “Optimal” curve, because “Optimal” denotes the best dual index policy rather than the true problem‐wide optimum.

Problem setting specifications
Symbol	Definition
$T$	Total time horizon
$X,Y,X\in Y$	Two random variables, and shorthand for $X$ measurable with respect to $Y$
$\mathcal{S},\mathcal{A},P,C,s_{1}$	State and action space, transition distribution, cost function, starting state
$\bar{C}$	Upper bound on one-step cost
$\Theta,\theta$	Policy class, and arbitrary policy in the policy class

Table 2: Common notation

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Algorithm	Condition	Regret	Time	Space
IOPEA	Bounded width $w$	$\tilde{O}(H\sqrt{wdT/\alpha})$	$O(w\log(T)+T^{1+\frac{d}{2}})$	$O(T^{\frac{d}{2}})$
IOPEA	$w=\|\Theta_{1}\|$	$\tilde{O}(H\sqrt{d}T^{\frac{d+1}{d+2}})$	$O(T)$	$O(T^{\frac{d}{d+2}})$
Agrawal and Jia (2022)	Convexity	$\sqrt{T}$ -scaling	$O(T)$	$O(T)$
Feedback graph ( Dann et al. 2020 )		$\tilde{O}\mathopen{}\mathclose{{\left(K^{\frac{d_{S}+p}{d_{S}+p+1}}}}\right)$	$O\mathopen{}\mathclose{{\left(K^{\frac{3d_{S}+d_{A}+p+1}{d_{S}+p+1}}}}\right)$	$O\mathopen{}\mathclose{{\left(K^{\frac{2d_{S}+d_{A}}{d_{S}+p+1}}}}\right)$

Appendix

Table 3: Comparison of regret, time, and space complexity under different structural assumptions. For Feedback Graph ( Dann et al. 2020 ) ,

p

denotes the growth rate of the mas-number

M

, i.e.,

M=O((1/r)^{p})

; more details in Dann et al. (2020) .

Figure 2: An empirical illustration of non‐convexity in the long‐run average cost with respect to the base‐stock levels

(z_{e}^{\theta},z_{r}^{\theta})

under the lost‐sales dual index policy. Parameters are

L_{r}=8

L_{e}=2

c_{r}=1

c_{e}=8

h=1

p=10

, and demand follows an exponential distribution with rate

3/40

. Costs are approximated by sample averages over

T=10^{5}

steps, evaluated on a grid

(z_{e}^{\theta},z_{r}^{\theta})\in\{0,5,10,\dots,200\}^{2}

Inventory Control
	Small-scale	Large-scale
Lead Time ( $L$ )	2	6
Holding Cost ( $h$ )	1	1
Lost-sales Penalty ( $p$ )	10	10
$\mathbb{P}(D_{t}=0)$ ( $\gamma$ )	0.3	0.3
Demand Support ( $d$ )	$[0,3]$	$[0,40]$

Appendix

Table 4: Parameter specifications for the numerical simulations.

Panel of Figure 3 — Figure 3: Numerical evidence on the applicability of I OPEA in the dual-index case study. Figure 3(a) examines the effective quantity governing $H$ and $\alpha$ , namely $\mathbb{E}[Y_{2}]$ , which can replace $\gamma^{-L_{r}}$ in the regret bound in Corollary 4.9 . Figure 3(b) reports the empirical Lipschitz constant $\hat{L}_{\Theta}$ , and Figure 3(c) reports the end-to-end burn-in period. Figure 3(a) and Figure 3(c) are plotted on log–log scales, while Figure 3(b) uses a logarithmic scale only for the $x$ -axis.

A lgorithm	Queuing
	Decaying Arrival Rate	Fixed Arrival Rate
Optimal $(g_{\theta^{*}})$	$9.5$	$11.6$
ERM ( Sinclair et al. 2023b )	$9.6(1\%)$	$11.6(0\%)$
I OPEA	${}^{\star}10.5(11\%)$	${}^{\star}13.1(13\%)$
PPO ( Schulman et al. 2017 )	${}^{\star}9.8(3\%)$	${}^{\star}11.8(2\%)$
Feedback Graph ( Dann et al. 2020 )	$11.5(21\%)$	$13.2(13\%)$

Appendix

Table 5: Queuing Performance under Decaying vs. Fixed Arrival Rates

Queueing Theory

See all 18 papers

Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
Mar 25, 2026Guy Zamir, Matthew Zurek, Yudong ChenRegret Minimization in RL Average-Reward RL
Department of Computer Sciences, University of Wisconsin–Madison
What Information Buys in Active Inference
Oct 13, 2026Melih Kandemir, Mustafa Mert ÇelikokRL Exploration Active Inference
Department of Mathematics and Computer Science, University of Southern Denmark
Average-Reward Policy Identification from a Single Continuing Trajectory
Oct 14, 2026Tongxi WangReinforcement Learning Average-Reward RL
Southeast University

Mar 25, 2026J/K move · Enter open · S save

Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs

Guy Zamir, Matthew Zurek, Yudong Chen

Department of Computer Sciences, University of Wisconsin–Madison

Regret Minimization in RL Average-Reward RL Minimax Regret

Open paper AskPDF arXiv

Online reinforcement learning in infinite-horizon Markov decision processes (MDPs) remains less theoretically and algorithmically developed than its episodic counterpart, with many algorithms suffering from high ``burn-in'' costs and failing to adapt to benign instance-specific complexity. In this work, we address these shortcomings for two infinite-horizon objectives: the classical average-reward regret and the

γ

-regret. We develop a single tractable UCB-style algorithm applicable to both settings, which achieves the first optimal variance-dependent regret guarantees. Our regret bounds in both settings take the form

\tilde{O}( \sqrt{SA\,\text{Var}} + \text{lower-order terms})

, where

S,A

are the state and action space sizes, and

\text{Var}

captures cumulative transition variance. This implies minimax-optimal average-reward and

γ

-regret bounds in the worst case but also adapts to easier problem instances, for example yielding nearly constant regret in deterministic MDPs. Furthermore, our algorithm enjoys significantly improved lower-order terms for the average-reward setting. With prior knowledge of the optimal bias span

\Vert h^\star\Vert_\text{sp}

, our algorithm obtains lower-order terms scaling as

\Vert h^\star\Vert_\text{sp} S^2 A

, which we prove is optimal in both

\Vert h^\star\Vert_\text{sp}

and

A

. Without prior knowledge, we prove that no algorithm can have lower-order terms smaller than

\Vert h^\star \Vert_\text{sp}^2 S A

, and we provide a prior-free algorithm whose lower-order terms scale as

\Vert h^\star\Vert_\text{sp}^2 S^3 A

, nearly matching this lower bound. Taken together, these results completely characterize the optimal dependence on

\Vert h^\star\Vert_\text{sp}

in both leading and lower-order terms, and reveal a fundamental gap in what is achievable with and without prior knowledge.

Abstract

Queueing Theory

Explore similar work

Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs

What Information Buys in Active Inference

Average-Reward Policy Identification from a Single Continuing Trajectory