Dynamic Programming

Why policy improvement matters

Reinforcement learning methods search for good behaviour by alternating two activities: estimating how good the current behaviour is, and changing the behaviour in the direction those estimates suggest. Sutton and Barto call this pattern generalized policy iteration and use it as the organizing idea of their textbook (Sutton & Barto 2018, §4.6). Its mathematical justification is a single result of Chapter 4, the policy improvement theorem (p. 78): a comparison made one step ahead, at each state separately, certifies that a changed policy is at least as good everywhere. Policy iteration, value iteration, Monte Carlo control with ε-greedy policies (Chapter 5), Sarsa and Q-learning are all motivated by it.

The chapter's results go back to the foundations of dynamic programming: the Bellman optimality equation (Bellman 1957), and policy iteration with its finite termination for discounted finite Markov decision processes (Howard 1960). Standard modern treatments are Puterman 1994, Ch. 6, and Bertsekas 2012, Vol. II, Ch. 1.

Setting

A finite Markov decision process has a finite state set $\mathcal S$, a finite nonempty action set $\mathcal A$, a finite reward set $\mathcal R\subset\mathbb R$ and dynamics $p(s', r\mid s, a)$: for each state $s$ and action $a$, a probability distribution over the next state $s'$ and reward $r$ (Eqs. (3.2)–(3.3)). A policy $\pi$ gives probabilities $\pi(a\mid s)$ of choosing each action in each state; a deterministic policy is a map $\pi:\mathcal S\to\mathcal A$.

Fix a discount rate $0\le\gamma<1$. The state-value function of $\pi$ is the expected discounted return

$$v_\pi(s) = E_\pi\Big[\sum_{k=0}^\infty \gamma^k R_{t+k+1}\ \Big|\ S_t=s\Big],$$

and the action-value function is defined from it by (4.6):

$$q_\pi(s,a) = \sum_{s',r} p(s',r\mid s,a)\,\big[r+\gamma v_\pi(s')\big],$$

the value of taking $a$ once in $s$ and following $\pi$ afterwards. A policy is optimal if its value is at least that of every policy at every state, and the optimal value function is $v_*(s)=\max_\pi v_\pi(s)$. A deterministic policy $\pi'$ is greedy with respect to $q_\pi$ if $\pi'(s)\in\operatorname{argmax}_a q_\pi(s,a)$ for all $s$ (4.9).

Formalization targets

Goal: the policy improvement theorem, (4.7)–(4.8), p. 78

For deterministic policies $\pi,\pi'$,

$$\big(\forall s,\ q_\pi(s,\pi'(s))\ge v_\pi(s)\big)\ \Longrightarrow\ \big(\forall s,\ v_{\pi'}(s)\ge v_\pi(s)\big),$$

and at every state where the hypothesis is strict, the conclusion is strict at that same state.

Milestones

1. Iterative policy evaluation (4.5), p. 74. From any $v_0$, the iterates $v_{k+1}(s)=\sum_a\pi(a\mid s)\sum_{s',r}p(s',r\mid s,a)[r+\gamma v_k(s')]$ converge to $v_\pi$.
2. Greedy improvement (4.9), p. 79. A greedy $\pi'$ with respect to $q_\pi$ satisfies (4.7), hence $v_{\pi'}\ge v_\pi$.
3. The stochastic case, p. 79. For stochastic $\pi,\pi'$, with $q_\pi(s,\pi'(s))=\sum_a\pi'(a\mid s)q_\pi(s,a)$ as in (5.2), the theorem holds as stated, strictness included.
4. Equality forces optimality, p. 79. If a greedy $\pi'$ has $v_{\pi'}=v_\pi$, then $v_{\pi'}$ solves the Bellman optimality equation (4.1), $v_{\pi'}=v_*$, and $\pi$ and $\pi'$ are optimal.
5. Policy iteration, p. 80. For every sequence of deterministic policies with $\pi_{k+1}$ greedy with respect to $q_{\pi_k}$: each step is a strict improvement unless $\pi_k$ is optimal, and from some $K$ on every $\pi_k$ is optimal with $v_{\pi_k}=v_*$.
6. Value iteration (4.10), p. 83. $v_*$ is attained by one policy at all states, and from any $v_0$ the iterates $v_{k+1}(s)=\max_a\sum_{s',r}p(s',r\mid s,a)[r+\gamma v_k(s')]$ converge to $v_*$.

Significance

The results. The policy improvement theorem turns a local test into a global guarantee: it is enough to check, state by state, that one step of the new policy followed by the old one does no worse than the old one. Combined with the finiteness of the set of deterministic policies, it yields the finite termination of policy iteration and, with the equality case, the existence of a deterministic optimal policy. The stochastic form is what Chapter 5 invokes for ε-greedy control. Value iteration is the other classical way to compute $v_*$.

Formalizing them. All of these results are classical and proved in the literature cited above; they are not open. The textbook presents them informally ("we chose not to produce a rigorous formal treatment", p. xiii): the improvement theorem is argued by an unbounded chain of expansions, and the policy evaluation and value iteration convergence claims are stated without proof. The mission makes each claim precise with explicit hypotheses and asks for machine-checked proofs against the book's own model with four-argument dynamics and stochastic policies. Related platform results use different models (cost minimization with deterministic policies in Bertsekas's Dynamic Programming; an expected-reward kernel and an assumed fixed point in Foundations of Machine Learning), and none states the policy improvement theorem itself.

Difficulty

The book's proof expands $q_\pi$ with (4.6) and reapplies (4.7) indefinitely, ending with "$\le\cdots=v_{\pi'}(s)$". Made rigorous, the chain is an inequality between truncated returns plus a remainder $\gamma^n E_{\pi'}[v_\pi(S_{t+n})]$, and the passage to the limit needs the remainder to vanish and the truncated returns to converge to $v_{\pi'}$. Since $v_\pi$ is defined here as a series of expected rewards under the induced Markov chain, connecting it to the one-step quantities requires first establishing the Bellman equation for $v_\pi$ from that series. The strictness part does not follow from the weak inequality alone: strictness at one state must be shown to survive the averaging over later states, which requires tracking the contribution of the first step exactly. The policy iteration statement additionally requires handling ties: a greedy step taken from an optimal policy can move to a different optimal policy, so the sequence need not become constant.

Formalization scope

All objects live in the namespace SuttonBartoRL.DP. States and actions are finite types, actions nonempty where a maximum is taken; one action set serves all states (footnote 3, p. 48). Rewards form a finite set $\mathcal R\subset\mathbb R$, and the dynamics are a function $p(s',r\mid s,a)$ whose values off $\mathcal R$ are never used. Policies are stochastic; deterministic policies are embedded as policies that choose one action with probability one.

Committed conventions:

• Discount $0\le\gamma<1$ throughout. The book also allows $\gamma=1$ when "eventual termination is guaranteed" (p. 74) but never states that hypothesis precisely; the episodic case with a terminal state is out of scope. This is the only restriction relative to the text.
• $v_\pi$ from returns. $v_\pi(s)=\sum_k\gamma^k(P_\pi^k r_\pi)(s)$, with $P_\pi$ the state transition matrix of $\pi$ and $r_\pi$ its expected one-step reward. $q_\pi$ is defined by (4.6), as the book does. The Bellman equation (4.4) is not assumed. Defining $v_\pi$ as the fixed point of a Bellman operator would make the goal an order property of that operator and is excluded.
• $v_*$ is the real supremum over all stochastic policies; the value iteration item also asserts it is attained. Optimality of a policy means dominance over all stochastic policies.
• Greedy means $\pi'(s)$ is any maximizer of $q_\pi(s,\cdot)$; tie-breaking is arbitrary and may differ between iterations.
• Stochastic case. The book only says the theorem "carries through as stated"; the meaning $q_\pi(s,\pi'(s))=\sum_a\pi'(a\mid s)q_\pi(s,a)$ is taken from the book's (5.2), p. 101.
• Policy iteration is the idealized sequence with exact evaluation. The item does not claim that the boxed pseudocode on p. 80 stops, which it may fail to do under ties (Exercise 4.4, p. 82).
• Convergence of iterates is in the product topology on $\mathbb R^{\mathcal S}$, equivalent to the sup norm for finite $\mathcal S$.

In-place (asynchronous) sweeps (§4.5) and truncated policy iteration are not formalized.

Needed infrastructure: summability of discounted series of bounded expected rewards, the Bellman equation for $v_\pi$ derived from the return definition, contraction arguments in the sup norm on $\mathbb R^{\mathcal S}$, and finiteness of the set of deterministic policies. The definitions here duplicate those of the series' Chapter 3 mission and are intended to be merged with them; lemmas about $v_\pi$, the Bellman equation and contraction are reusable by every later mission of the series, and contributions of such lemmas are welcome.

Selected references

• R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, 2nd ed., MIT Press, 2018, ISBN 9780262039246, Chapter 4. http://incompleteideas.net/book/the-book-2nd.html
• R. Bellman, Dynamic Programming, Princeton University Press, 1957. https://press.princeton.edu/books/paperback/9780691146683/dynamic-programming
• R. A. Howard, Dynamic Programming and Markov Processes, MIT Press, 1960. https://mitpress.mit.edu/9780262080095/dynamic-programming-and-markov-processes/
• M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley, 1994. https://doi.org/10.1002/9780470316887
• D. P. Bertsekas, Dynamic Programming and Optimal Control, Vol. II, 4th ed., Athena Scientific, 2012. http://www.athenasc.com/dpbook.html

Motivation

Sutton and Barto's Reinforcement Learning: An Introduction (2nd ed., MIT Press, 2018) is the standard introductory text of the field. Its Chapter 3 sets up the model that the rest of Part I works in: the finite Markov decision process (MDP), the value functions of a policy, and the Bellman equations that relate the value of a state to the values of its successors. Section 3.6 then states the fact every planning and control method of the book relies on: in a finite MDP there is an optimal policy, its value is the unique solution of a system of nonlinear equations, and a policy that acts greedily with respect to that solution is optimal. Dynamic programming (Chapter 4), Monte Carlo control (Chapter 5), Sarsa and Q-learning (Chapter 6) are all methods for solving the Bellman optimality equation; their correctness statements presuppose that it has exactly one solution and that it identifies optimal behaviour.

The book is deliberately informal ("we chose not to produce a rigorous formal treatment", p. xiii): §3.6 asserts these facts without proof. The results themselves are classical, going back to Bellman (1957), Howard (1960) and Blackwell (1965); a textbook proof for discounted finite MDPs is in Puterman, Markov Decision Processes (Wiley, 1994), Chapter 6.

Setting

A finite MDP has a finite set of states $\mathcal S$, a finite nonempty set of actions $\mathcal A$, a finite set of rewards $\mathcal R \subset \mathbb R$, and dynamics

$$p(s', r \mid s, a) = \Pr\{S_t = s', R_t = r \mid S_{t-1} = s, A_{t-1} = a\}, \qquad \sum_{s' \in \mathcal S}\sum_{r \in \mathcal R} p(s', r \mid s, a) = 1,$$

Eqs. (3.2)–(3.3). From $p$ one derives $p(s' \mid s, a) = \sum_r p(s', r \mid s, a)$ and $r(s, a) = \sum_r r \sum_{s'} p(s', r \mid s, a)$, Eqs. (3.4)–(3.5).

A policy $\pi$ gives a probability $\pi(a \mid s)$ of each action in each state. Fix a discount rate $0 \le \gamma < 1$. The return of a reward sequence is $G_t = \sum_{k \ge 0} \gamma^k R_{t+k+1}$ (3.8). The state-value function and action-value function of $\pi$ are the expected returns

$$v_\pi(s) = \mathbb E_\pi[G_t \mid S_t = s], \qquad q_\pi(s, a) = \mathbb E_\pi[G_t \mid S_t = s, A_t = a] \qquad (3.12)\text{–}(3.13).$$

In the Lean development these are stateValue M γ π s and actionValue M γ π s a, computed as $\sum_k \gamma^k (P_\pi^k r_\pi)(s)$ from the transition matrix $P_\pi(s, s') = \sum_a \pi(a \mid s)\,p(s' \mid s, a)$ and the expected reward $r_\pi(s) = \sum_a \pi(a \mid s)\,r(s, a)$ of the Markov chain the policy induces. A policy $\pi$ is optimal (IsOptimalPolicy) if $v_\pi(s) \ge v_{\pi'}(s)$ for every policy $\pi'$ and every state $s$. The optimal value functions are

$$v_*(s) = \max_\pi v_\pi(s) \quad (3.15), \qquad q_*(s, a) = \max_\pi q_\pi(s, a) \quad (3.16),$$

optimalValue and optimalActionValue, with the maximum over all stochastic policies.

Formalization targets

Goal: the Bellman optimality equation and optimal policies (§3.6, pp. 62–64)

For every finite MDP and $0 \le \gamma < 1$:

1. the maximum in (3.15) is attained at every state;
2. an optimal policy exists;
3. $v_*$ satisfies the Bellman optimality equation

$$v_*(s) = \max_{a} \sum_{s', r} p(s', r \mid s, a)\big[r + \gamma v_*(s')\big] \quad \text{for all } s; \qquad (3.19)$$

4. $v_*$ is the only function on $\mathcal S$ satisfying (3.19);
5. every policy that assigns positive probability only to actions attaining the maximum in (3.19) is optimal.

Milestones

• (3.9) $G_t = R_{t+1} + \gamma G_{t+1}$ for bounded rewards, with the series convergent.
• (3.14) the Bellman equation $v_\pi(s) = \sum_a \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a)[r + \gamma v_\pi(s')]$, and (p. 60) its uniqueness: $v_\pi$ is its only solution.
• Exercise 3.15 adding a constant $c$ to all rewards adds $v_c = c/(1-\gamma)$ to every value.
• Exercises 3.18 and 3.19 $v_\pi(s) = \sum_a \pi(a \mid s)\,q_\pi(s, a)$ and $q_\pi(s, a) = \sum_{s', r} p(s', r \mid s, a)[r + \gamma v_\pi(s')]$.
• (3.16)–(3.17) the maximum defining $q_*$ is attained and $q_*(s, a) = \sum_{s', r} p(s', r \mid s, a)[r + \gamma v_*(s')]$.
• (3.20) the Bellman optimality equation for action values, $q_*(s, a) = \sum_{s', r} p(s', r \mid s, a)[r + \gamma \max_{a'} q_*(s', a')]$.

Significance

The goal is what turns "find a good policy" into "solve a system of equations". Parts 3 and 4 identify $v_*$ with the unique solution of (3.19), so any procedure that finds a solution of (3.19) has found $v_*$; part 5 converts $v_*$ into an optimal policy by a one-step search. Parts 1 and 2 say that the book's definition (3.15) makes sense: a single policy is simultaneously best at every state, so "the optimal value function" is well defined and shared by all optimal policies. Chapter 4's policy iteration and value iteration, and the fixed points of Q-learning, are statements about this equation. Exercises 3.18 and 3.19 are used, by number, in the proof of the policy gradient theorem (p. 325).

The mathematics is classical and proved in many texts; what is missing is a machine-checked version in the book's own model. Platform relatives exist in different models: FoundationsML.ReinforcementLearning.bellman_equations_unique_solution (uniqueness for a fixed policy, with an expected-reward kernel instead of $p(s', r \mid s, a)$), BertsekasDP.discounted_main_theorem (cost minimization over deterministic stationary policies), BanditAlgorithm.mdp_discounted_bellman_solution (existence of a solution with a greedy deterministic policy, rewards in $[0,1]$) and FoundationsRL.RLBasics.bellman_optimality (finite horizon). None of them states the book's result: the four-argument dynamics, stochastic policies, the maximum over all of them, uniqueness of the solution of (3.19), and optimality of every policy supported on greedy actions. This mission produces that statement and, with it, a vocabulary of finite-MDP definitions that the later missions of the series reuse.

Difficulty

The book's derivation of (3.19) (p. 63) starts from $v_*(s) = \max_a q_{\pi_*}(s, a)$ with a policy $\pi_*$ that is optimal at every state at once. The existence of such a policy is the substance of the goal, and it does not follow from the definition: (3.15) takes a separate maximum at each state, and a priori the maximizing policy could depend on the state. Uniqueness for (3.19) is likewise not a consequence of linear algebra, as it is for (3.14): the equation is nonlinear because of the maximum. The fixed point must be related to the value of an actual policy, and every policy's value must be bounded above by it.

Formalization scope

• Model. S and A are finite types with A nonempty (without an action, $\max_a$ is undefined). One action set serves every state, as the book's footnote 3 (p. 48) allows. Rewards form a finite set M.R : Finset ℝ and the dynamics are the four-argument M.p s a s' r with the normalization (3.3).
• Discounting. All statements assume $0 \le \gamma < 1$ (the continuing discounted case of §3.3). The episodic case with $\gamma = 1$ is not covered: the book's uniqueness claims then need every episode to terminate under every policy, which the chapter never states, and without it (3.19) can have many solutions (a state that loops to itself with reward $0$ satisfies $v(s) = v(s)$ for any value).
• Value functions from returns. $v_\pi$ and $q_\pi$ are expected discounted returns, computed from the Markov chain the policy induces. They are not defined as solutions of the Bellman equations, and $v_*$ is not defined as a solution of (3.19): either would make the goal true by definition. The Bellman equations are theorems.
• Maxima. $v_*$ and $q_*$ are real suprema over the type of stochastic policies (Lean gives a supremum that does not exist the value $0$); the goal and milestone (3.17) assert that these suprema are attained, so they are the book's maxima.
• Conditional expectations. (3.17), (3.18) and (3.20) are stated in their finite-sum form over $(s', r)$.
• Exercises. Exercises 3.15, 3.18 and 3.19 have no printed solutions; the statements give the formalization's answers ($v_c = c/(1-\gamma)$ and the two displayed identities).
• Reusable infrastructure. The definitions (MDP, Policy, trans, expReward, policyTrans, policyReward, stateValue, actionValue, optimalValue, optimalActionValue, IsOptimalPolicy) follow the conventions shared by the whole series and are meant to be merged with the finite-MDP layers of the later chapters. Lemmas on summability of the value series, the Bellman operator as a $\gamma$-contraction in the sup norm, and the Markov-chain identities for $P_\pi^k$ are welcome as separate contributions.

Selected references

• R. S. Sutton, A. G. Barto, Reinforcement Learning: An Introduction, 2nd ed., MIT Press, 2018, ISBN 9780262039246, Chapter 3. http://incompleteideas.net/book/the-book-2nd.html
• R. Bellman, Dynamic Programming, Princeton University Press, 1957. https://doi.org/10.2307/j.ctv1nxcw0f
• R. A. Howard, Dynamic Programming and Markov Processes, MIT Press, 1960.
• D. Blackwell, "Discounted dynamic programming", Annals of Mathematical Statistics 36(1), 1965, 226–235. https://doi.org/10.1214/aoms/1177700285
• M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley, 1994. https://doi.org/10.1002/9780470316887

Why multi-stage games

Chapter X of Richard Bellman's Dynamic Programming (Princeton University Press, 1957; Princeton Landmarks edition 2010, DOI 10.2307/j.ctv1nxcw0f) carries the functional-equation method of the earlier chapters from one-player decision processes to two-player zero-sum games that are played over many stages. At each stage the two players make simultaneous choices, and those choices change the state in which the next stage is played. Games of survival are the standard example. They generalize the gambler's ruin: two players with finite resources play until one of them is ruined. The same framework is the discrete-time form of what Shapley (1953) called stochastic games. It underlies pursuit games, attrition models and the later theory of dynamic games in operations research and economics.

The chapter builds on von Neumann's min-max theorem (1928), which Bellman assumes without proof (§ 3, Eq. (3.4)). It proves three kinds of result: existence and uniqueness for the general multi-stage game equation (§§ 11–16), existence and uniqueness for games of survival with integer payoffs (§ 19), and an extended min-max theorem for ratios of bilinear forms (§ 23). Bellman proposes the ratio as a criterion for non-zero-sum games.

Setting

A matrix game is given by a real $M\times N$ matrix $A=(a_{ij})$. Player $A$ chooses row $i$ with probability $p_i$ and player $B$ chooses column $j$ with probability $q_j$; $p$ and $q$ are distribution vectors (points of the standard simplex). The expected return to $A$ is

$$E_A(p,q)=\sum_{i,j}a_{ij}\,p_i\,q_j .$$

The game has value $v$ when $\max_p\min_q E_A=v=\min_q\max_p E_A$, all extrema attained. In the Lean development this is IsMaxMinMinMaxValue, and the bilinear form is bilin.

In the general multi-stage game (§ 12) the state is a pair of vectors $P\in D\subseteq\mathbb R^n$, $P'\in D'\subseteq\mathbb R^{n'}$ with norms $\|P\|=\sum_i|P_i|$. In state $(P,P')$, $A$ chooses $u$ in a choice domain $S(P,P')$ and $B$ chooses $v$ in $S'(P,P')$. $A$ receives $R(u,v)$, and play continues from the state $T(P,P';u,v)$, $T'(P,P';u,v)$ with weight $h(P,P';u,v)$. Mixed strategies $G$, $G'$ are probability measures on the choice domains. The multi-stage game equation is

$$f(P,P')=\max_G\min_{G'}\iint\big[R(u,v)+h(P,P';u,v)\,f(T,T')\big]\,dG(u)\,dG'(v)=\min_{G'}\max_G[\ \cdots\ ].$$

A game of survival with integer payoffs (§ 19) has one integer state $x$, the resources of $A$ out of a fixed total $d$. $A$ is ruined at $x\le0$ and wins at $x\ge d$. At each stage the players play the $2\times2$ game with matrix $\begin{pmatrix}-1&a\\c&-b\end{pmatrix}$, whose entries are the transfers to $A$.

Formalization targets

Goal: the extended min-max theorem (Chapter X, Theorem 7)

For real matrices $A=(a_{ij})$, $B=(b_{ij})$ with $\sum_{i,j}b_{ij}p_iq_j\ge d>0$ for all distribution vectors $p,q$,

$$\max_p\min_q\frac{\sum_{i,j}a_{ij}p_iq_j}{\sum_{i,j}b_{ij}p_iq_j}=\min_q\max_p\frac{\sum_{i,j}a_{ij}p_iq_j}{\sum_{i,j}b_{ij}p_iq_j}.$$

It is the chapter's final result, and its statement involves only finite matrices.

Milestones

1. Eq. (3.4), von Neumann's theorem $V_A=V_B$. It is already on the platform as AGT.zero_sum_minimax (existence of a saddle point) and enters as a reference.
2. Lemma 1: the value of a one-stage game moves by at most the largest change of its kernel, $|L(f)-L_1(F)|\le\max_{u,v}\,[\,|R-R_1|+|h|\,|f(T,T')-F(T,T')|\,]$.
3. Theorem 1: under hypotheses (4a)–(4e), the multi-stage game equation has a unique solution among functions continuous on $D\times D'$ that vanish at the origin, and it is the uniform limit on bounded regions of the successive approximations.
4. Theorem 3: the successive approximations converge from any admissible initial function.
5. Theorem 4: stability, $|f(P,P')-F(P,P')|\le\sum_{n\ge0}\Delta(k^nc)$.
6. Theorem 5: the game of survival equation with boundary values $0$ and $1$ has a unique solution with values in $[0,1]$.

Significance

Theorem 7 gives a value for ratio games, the games in which a player maximizes a return per unit of a resource consumed. Bellman uses it to give a rationale for the play of non-zero-sum games (§ 24) and to derive the approximate equation (22.4) for non-zero-sum games of survival. Chapter XI, Theorem 5 generalizes it to Markovian decision processes. Theorem 1 is the existence and uniqueness result that justifies replacing an infinite game by its functional equation, and Theorems 3 and 4 make that equation usable for computation and perturbation. Theorem 5 is an early uniqueness theorem for a discrete stochastic game with absorbing boundaries.

None of these statements is formalized on the platform. Von Neumann's theorem is (AGT.zero_sum_minimax, and Sion's theorem as FamousTheorems.sion_minimax_theorem). Theorem 7 is a classical result: with a positive denominator the ratio is quasiconcave in $p$ and quasiconvex in $q$. This mission asks for a machine-checked proof of the book's statement, by Bellman's route or by any other. Theorems 1, 3 and 4 need a formal theory of games whose mixed strategies are probability measures on moving compact choice domains. No such theory is on the platform yet.

Difficulty

The ratio in Theorem 7 is not bilinear, and in general it is neither concave in $p$ nor convex in $q$, so neither von Neumann's theorem nor a concave-convex min-max theorem applies to it directly. For Theorem 1, the contraction argument needs each one-stage game to have a value and the value to depend continuously on the state. That requires a min-max theorem for continuous games on compact sets, together with continuity of the value when the choice domains move. In Theorem 5, existence follows from monotone iteration. The uniqueness step is the hard part: the operator is not a contraction in the sup norm, and a second solution must be ruled out even at states where the optimal mixed strategies are degenerate.

Formalization scope

• Distribution vectors are points of stdSimplex ℝ ι for nonempty finite types. "Max-min equals min-max" always asserts attainment (IsGreatest/IsLeast) and never uses sSup/sInf, which return $0$ on empty or unbounded sets. Theorem 7 must not assume a saddle point; its only hypothesis is the bound on the denominator.
• States are Fin n → ℝ with the $\ell^1$ norm of Eq. (12.1). Choice domains are nonempty compact sets (NonemptyCompacts), and mixed strategies are probability measures of full mass on them. "Vary continuously" in (4b), which the book does not define, is read as continuity in Mathlib's topology on nonempty compact sets (for a metric space, the topology of the Hausdorff distance).
• The maxima $w(c)$ of (4d) and $\Delta(c)$ of Theorem 4 are expressed through majorants, which is equivalent to the book's condition. $k\ge0$ is stated explicitly. In Lemma 1 the kernels are assumed measurable and bounded on $S\times S'$ so that the integrals exist, and each game having a value is a hypothesis, as in Bellman's footnote 4.
• Theorem 3's "converges" is stated as uniform convergence on bounded regions, the mode of Theorem 1, whose proof Theorem 3 repeats. Theorem 4's unspecified $c$ is any $c\ge\|P\|+\|P'\|$. The book's p. 301 prints the first min-max of Theorem 4 with the subscripts $G$, $G'$ interchanged; the equation used is that of Theorem 1.
• Theorem 5 adds the implicit $d\ge1$: for $d\le0$ the boundary conditions contradict each other. The state is an integer and $f:\mathbb Z\to\mathbb R$.
• Taking the choice domains constant would trivialize Theorem 1: condition (4d) would then force $R\equiv0$ on them. The choice domains therefore depend on the state.
• Not included: Theorem 2 (optimal strategies of the infinite game, which needs a model of the game's plays), Theorem 6 (non-zero-sum survival; the boundary conditions (21.3) do not cover all states, see the moderation notes).

Contributions of reusable infrastructure are welcome: the min-max theorem for continuous games on compact sets (Eq. (4.2)), continuity of the value in the choice domains, and value iteration for contracting game operators.

Selected references

• R. Bellman, Dynamic Programming, Princeton University Press, 1957; Princeton Landmarks in Mathematics, 2010. DOI 10.2307/j.ctv1nxcw0f
• J. von Neumann, Zur Theorie der Gesellschaftsspiele, Mathematische Annalen 100, 1928. DOI 10.1007/BF01448847
• L. S. Shapley, Stochastic games, Proceedings of the National Academy of Sciences 39, 1953. DOI 10.1073/pnas.39.10.1095
• M. Sion, On general minimax theorems, Pacific Journal of Mathematics 8, 1958. DOI 10.2140/pjm.1958.8.171
• I. L. Glicksberg, A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points, Proceedings of the AMS 3, 1952. DOI 10.1090/S0002-9939-1952-0046638-5

Motivation

Many queueing systems evolve in continuous time: customers arrive according to a Poisson process, services take exponentially distributed times, and a controller may change the service rate, admit or reject customers, or route them whenever the state changes. Minimizing the long-run average cost of such a system is a standard problem in the control of queues (Lippman 1975; Puterman 1994, Ch. 11; Sennott 1999, Ch. 10). The continuous time model does not fit directly into the discrete time theory of Markov decision chains developed in the earlier chapters of Sennott's book, because time spent in a state now matters and the natural average cost is a ratio of expected cost to expected elapsed time.

This mission formalizes Sections 10.1–10.4 of L. I. Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems (Wiley, 1999): the elementary properties of the exponential distribution, the continuous time Markov decision chain and its average cost, a reduction of the continuous time problem to an auxiliary discrete time Markov decision chain, and the theorem stating that finite state approximating sequences of the auxiliary chain compute optimal average costs and optimal stationary policies of the continuous time chain. The chapter closes with an explicit average cost computation for the M/M/1 queue with service rate control.

Setting

A random variable $X$ has the exponential distribution with rate $\mu>0$ if $P(X\le t)=1-e^{-\mu t}$ for $t\ge0$. A function $r(\delta)$ is $o(\delta)$ if $r(\delta)/\delta\to0$ as $\delta\to0^+$.

A continuous time Markov decision chain (CTMDC) $\Psi$ has a countable state space $S$ and, for each $i\in S$, a finite nonempty action set $A_i$. Choosing $a\in A_i$ in state $i$ incurs an instantaneous cost $G(i,a)\ge0$ and a cost rate $g(i,a)\ge0$ in effect until the next transition. The time until the next transition is exponential with rate $\nu(i,a)>0$, so its mean is $\tau(i,a)=1/\nu(i,a)$; the next state is $j$ with probability $P_{ij}(a)$, where $P_{ii}(a)=0$. A policy $\theta$ chooses, at each transition, an action (possibly at random) from the history of past states, actions and sojourn times; a stationary policy $e$ chooses $e(i)$ in state $i$. With $C_n$ the cost and $T_n$ the time of the first $n$ transition periods, the average cost and the minimum average cost are

$$J^\Psi_\theta(i)=\limsup_{n\to\infty}\frac{E_\theta[C_n\mid X_0=i]}{E_\theta[T_n\mid X_0=i]},\qquad J^\Psi(i)=\inf_\theta J^\Psi_\theta(i).$$

Assumption (CTB) requires constants $\tau$ and $B$ with $0<\tau<\inf_{i,a}\tau(i,a)\le\sup_{i,a}\tau(i,a)\le B<\infty$. The auxiliary MDC $\Delta$ has the same states and actions, costs $C(i,a)=G(i,a)\nu(i,a)+g(i,a)$, and transition probabilities $P^*_{ij}(a)=\tau\nu(i,a)P_{ij}(a)$ for $j\ne i$, $P^*_{ii}(a)=1-\tau\nu(i,a)$. Its average cost $J^\Delta_\theta(i)=\limsup_n n^{-1}\sum_{t<n}E_\theta[C(X_t,Y_t)]$ and minimum average cost $J^\Delta(i)$ are those of Chapter 2. Assumption (CTAC) is $J^\Delta(\cdot)\le J^\Psi(\cdot)$.

An approximating sequence $(\Delta_N)_{N\ge N_0}$ for $\Delta$ uses finite state spaces $S_N$ increasing to $S$ and transition probabilities $P^*_{ij}(a;N)$ on $S_N$ converging to $P^*_{ij}(a)$. The (AC) assumptions ask for constants $J^N$ and functions $r^N$ on $S_N$ solving

$$J^N+r^N(i)=\min_{a\in A_i}\Big\{C(i,a)+\sum_{j\in S_N}P^*_{ij}(a;N)\,r^N(j)\Big\},\qquad i\in S_N,\ N\ge N_0,\tag{10.21}$$

with $\limsup_N r^N(i)<\infty$, $\liminf_N r^N(i)\ge-Q$ for a constant $Q\ge0$, and $\limsup_N J^N=:J^*<\infty$, $J^*\le J^\Delta(i)$.

Formalization targets

Goal: Theorem 10.3.3

Under (CTB), (CTAC) and the (AC) assumptions for an approximating sequence of $\Delta$:

$$J^*=\lim_{N\to\infty}J^N\ \text{exists and}\ J^\Delta(i)=J^\Psi(i)=J^*\quad(i\in S),$$

and every limit point $e^*$ of a sequence $e^N$ of stationary policies realizing the minimum in (10.21) satisfies $J^\Delta_{e^*}=J^\Delta$ and $J^\Psi_{e^*}=J^\Psi$. The goal leaves the chain, the approximating sequence and the constants of (CTB) arbitrary.

Milestones

• Proposition 10.1.2: $P(X>x+y\mid X>y)=P(X>x)$ for $x,y>0$, and $P(X\le\delta)=\mu\delta+o(\delta)$.
• Proposition 10.1.3: for independent exponentials, $P(X_1\le\delta,X_2\le\delta)=o(\delta)$, $P(X_1<X_2)=\mu_1/(\mu_1+\mu_2)$, and $\min(X_1,X_2)$ is exponential with rate $\mu_1+\mu_2$.
• Lemma 10.3.1: if $z$ is bounded below and $Z\tau(i,e)+z(i)\ge G(i,e)+g(i,e)\tau(i,e)+\sum_jP_{ij}(e)z(j)$ for all $i$ (10.15), then $J^\Psi_e\le Z$.
• Lemma 10.3.2: $(Z,w)$ satisfies $Z+w(i)\ge C(i,e)+\sum_jP^*_{ij}(e)w(j)$ (10.20) if and only if $(Z,\tau w)$ satisfies (10.15).
• Proposition 10.4.1: in the M/M/1 queue with arrival rate $\lambda$, holding cost $H(i)=Hi$ and service cost rate $c(a)$, the policy that always serves at rate $a>\lambda$ has average cost $\rho_ac(a)+H\rho_a/(1-\rho_a)$, $\rho_a=\lambda/a$.

Significance

The goal theorem turns the average cost control of a continuous time chain on an infinite state space into a finite computation: solve the optimality equation (10.21) of a finite truncation of the auxiliary chain, let the truncation grow, and read off the optimal average cost and an optimal stationary policy of the original continuous time chain. The auxiliary chain is the book's form of uniformization, and the result is what licenses the numerical study of the M/M/1 service rate control problem in Section 10.4 and of the M/M/K and polling models in Sections 10.5–10.6. Proposition 10.4.1 gives the closed-form benchmark against which the computed optimal policy is compared.

The results are proved in the book, some with details left to the reader (Lemma 10.3.2(ii), Problem 10.10), and the goal rests on Theorem 8.1.1 and Lemma 7.2.1 of the same book. None of them has, as far as a search of Mathlib and the Prove2Me catalogue shows, a machine-checked proof: Mathlib provides the exponential law (ProbabilityTheory.expMeasure) and its distribution function, but not memorylessness or the minimum of independent exponentials, and no continuous time Markov decision model. A formalization would supply these, together with a checked average cost comparison between a continuous time chain and its discrete time auxiliary chain.

Difficulty

The obvious argument compares the two chains policy by policy, but the policy classes differ: a policy for $\Delta$ may change action in every time slot, including slots where the state does not change, while a policy for $\Psi$ acts only at transitions and may use the observed sojourn times. Only the stationary policies coincide. The lower bound $J^\Psi\ge J^*$ therefore cannot be obtained by transferring policies, and it is exactly what Assumption (CTAC) supplies. The upper bound requires passing from the discrete time inequality (10.20) for the limit point $e^*$ to a bound on a ratio of expected cost to expected time in continuous time, where the denominator depends on the policy; the uniform bounds of (CTB) on the mean sojourn times are what control it. Inside Lemma 10.3.1 the function $z$ is only bounded below, so the telescoping of expectations must be justified without integrability of $z$ from above.

Formalization scope

The state space is a countable type S, actions a type Act, and action sets A i : Finset Act; the CTMDC and MDC structures hold data, and their axioms (nonempty action sets, nonnegative costs, positive rates, stochastic transition rows with $P_{ii}(a)=0$) are separate predicates. Transition probabilities are ℝ≥0∞-valued; costs, rates and the functions $z,w,r^N$ are real. Expected costs, expected times and all average costs are ℝ≥0∞-valued, so $+\infty$ is a legitimate value, and they are compared with real constants in EReal; the limits superior and inferior of (AC) are taken in EReal. The expected cost of $n$ transition periods under a general policy is a recursion over the periods in which the sojourn time is integrated against expMeasure ν(i,a) and the next state is drawn independently from $P_{i\cdot}(a)$; policies are measurable in the past sojourn times. In (10.15) and (10.20) the convergence of the series is part of the inequality. The strict inequality $\tau<\inf\tau(i,a)$ of (CTB) is kept strict (as a positive margin); weakening it to $\le$ would make $P^*_{ii}(a)$ vanish or turn negative.

The average cost $J^\Psi_\theta$ is a ratio of expectations, not the expectation of a ratio, and the infimum $J^\Psi$ ranges over history dependent randomized policies that may use sojourn times; replacing either by a stationary-only class, or dropping (CTAC), gives a different theorem.

A complete development needs: expected rewards of a chain with exponential holding times, the average cost theory of Chapter 8 for the auxiliary chain (Theorem 8.1.1 and Lemma 7.2.1, restated here as needed), and renewal-reward reasoning for Proposition 10.4.1. The exponential-distribution lemmas are reusable beyond this mission and are welcome as independent contributions.

Selected references

• L. I. Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems, Wiley Series in Probability and Statistics, John Wiley & Sons, 1999. https://doi.org/10.1002/9780470317037
• M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons, 1994. https://doi.org/10.1002/9780470316887
• S. A. Lippman, Applying a new device in the optimization of exponential queuing systems, Operations Research 23(4), 687–710, 1975. https://doi.org/10.1287/opre.23.4.687
• D. Gross and C. M. Harris, Fundamentals of Queueing Theory, 3rd ed., John Wiley & Sons, 1998.

Motivation

Control problems for queueing systems (admission control, service rate control, routing to parallel servers) are naturally modelled as Markov decision chains whose state is a vector of queue lengths. The state space is therefore denumerably infinite, and the performance measure of interest is usually the long-run average cost per slot. For such models the existence theory of average cost optimal stationary policies is well developed (Chapter 7 of Sennott's book), but existence gives no algorithm: an optimal policy is a function on an infinite set, and value iteration cannot be run on an infinite state space.

The approximating sequence method answers this by replacing the infinite model $\Delta$ with a sequence of finite models $\Delta_N$ on truncated state spaces $S_N$, solving the average cost optimality equation in each, and passing to the limit. Chapter 8 of L. I. Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems (Wiley, 1999) gives a set of conditions, the (AC) assumptions, under which this limit procedure provably produces the minimum average cost and an average cost optimal policy of $\Delta$.

Timeline. The approximating sequence method for the average cost criterion and the (AC) assumptions were introduced in Sennott (1997a), with further results in Sennott (1997b) (bibliographic notes, p. 194). The book collects these results, adds the four step verification template (Proposition 8.2.1), the finite-set augmentation route based on the (BOR) assumptions (Proposition 8.2.3), and the weakening (WAC) of Section 8.7, which Chapter 9 uses.

Setting

An MDC $\Delta$ has a countable state space $S$, a finite nonempty action set $A_i$ in each state $i$, a finite cost $C(i,a)\ge0$, and transition probabilities $P_{ij}(a)$. A general policy $\theta$ chooses actions at random using the whole past history. Its average cost is

$$J_\theta(i)=\limsup_{n\to\infty}\frac1n\sum_{t=0}^{n-1}E_\theta[C(X_t,A_t)\mid X_0=i],$$

and the minimum average cost is $J(i)=\inf_\theta J_\theta(i)\in[0,\infty]$. A policy is average cost optimal if $J_\theta\equiv J$.

An approximating sequence $(\Delta_N)_{N\ge N_0}$ consists of finite sets $S_N$ increasing to $S$ and MDCs $\Delta_N$ on $S_N$ with the same actions and costs and with transition probabilities $P_{ij}(a;N)$ on $S_N$ converging to $P_{ij}(a)$. Write $v^N_n$ and $V^N_\alpha$ for the $n$-horizon and discounted value functions of $\Delta_N$.

The (AC) assumptions are:

• (AC1) there are finite constants $J^N$ and finite functions $r^N$ on $S_N$ with

$$J^N+r^N(i)=\min_a\Big\{C(i,a)+\sum_{j\in S_N}P_{ij}(a;N)\,r^N(j)\Big\},\qquad i\in S_N; \tag{8.1}$$

• (AC2) $\limsup_N r^N(i)<\infty$;
• (AC3) $\liminf_N r^N(i)\ge -Q$ for a constant $Q\ge0$;
• (AC4) $J^*:=\limsup_N J^N<\infty$ and $J^*\le J(i)$ for all $i$.

The (WAC) assumptions of Section 8.7 allow $Q$ to depend on the state, at the price of integrability conditions along every stationary policy.

Formalization targets

Goal: Theorem 8.1.1

Under (AC), the limit $\lim_{N\to\infty}J^N$ exists and

$$J(i)=\lim_{N\to\infty}J^N\qquad\text{for all } i\in S,$$

and every limit point $e^*$ of stationary policies $e^N$ realizing the minimum in (8.1) is average cost optimal for $\Delta$. The statement fixes no constants; it asserts the shape of the conclusion for any model satisfying (AC).

Milestones

• Proposition 8.2.1 (the four step template): unichain and aperiodicity of the finite models, an $x$ standard policy at which the approximating sequence is conforming, a comparison of $v^N_n$ (or $V^N_\alpha$) with $v_n$ (or $V_\alpha$), and a lower bound on $v^N_n - v^N_n(x)$ together imply that the value iteration limits

$$r^N(i)=\lim_{n\to\infty}\big(v^N_n(i)-v^N_n(x)\big)$$

exist and satisfy (AC).

• Corollary 8.2.2: on $S=\{0,1,2,\dots\}$ with $S_N=\{0,\dots,N\}$ and excess probability sent to $N$, monotonicity of $v^N_n$, $v_n$ and of the first passage moments of a $0$ standard policy suffices.
• Proposition 8.2.3: an augmentation type approximating sequence that sends excess probability to a finite set of cheap states satisfies the template.
• Proposition 8.5.1: in the single-server queue with Bernoulli($p$) arrivals and constant service rate $a>p$,

$$J_{d(a)}=\frac{Hp(1-p)}{a-p}+\frac{pC(a)}{a}.$$

• Proposition 8.7.1: the conclusions of Theorem 8.1.1 hold under (WAC).

Significance

The result itself. Theorem 8.1.1 is what turns the existence theory of Chapter 7 into a computation. It certifies that the minimum average costs of the truncations converge to the minimum average cost of the infinite model, that this cost is constant, and that the policies produced by value iteration on $\Delta_N$ converge, along subsequences, to an optimal policy for $\Delta$. Propositions 8.2.1–8.2.3 reduce (AC) to properties that can be checked model by model; Section 8.3 checks them for queues with reject option, service rate control, and routing to parallel queues. Proposition 8.7.1 is the version used in Chapter 9 for models whose relative values are not uniformly bounded below. Proposition 8.5.1 gives the closed-form open-loop benchmark used in the numerical study of Section 8.5.

Formalizing it. All results are proved in the book; none has a machine-checked proof. A formalization would give the first verified convergence theorem for truncations of denumerable-state average cost MDPs, and would make the approximating sequence method usable as a certified reduction from infinite to finite models. The template results (8.2.1–8.2.3) additionally require a formal treatment of conformity of approximating Markov chains (Appendix C.4–C.5), which is of independent use.

Difficulty

The naive argument takes limits in (8.1) along $N$: the minimum over $a$ and the finite sums pass to the limit only in the inequality direction, and only after a Fatou-type lemma for sums against the converging distributions $P_{ij}(a;N)$ with integrands $r^N$ that are neither bounded nor monotone. The lower bound $-Q$ in (AC3) is exactly what makes this possible; without it the limit inequality can fail. The limit inequality then produces only an average cost optimality inequality, and turning it into optimality of the limit policy requires a separate argument that a function bounded below and satisfying the inequality yields an upper bound on the average cost. Existence of $\lim_N J^N$ is not given: (AC4) controls only the limit superior, and the limit must be identified through every subsequence. For the template results, the difficulty is in the Markov chain side: the convergence of first passage times and costs of the truncated chains, which fails for general approximating sequences (Examples C.4.4, C.4.7).

Formalization scope

The Lean development is in the namespace SennottDP.AvgASM. The state space is any countable type; action sets are Finsets, assumed nonempty; costs are finite and nonnegative (ℝ≥0); transition probabilities are ℝ≥0∞-valued, with each row a probability distribution for admissible actions. All value functions and average costs take values in $[0,\infty]$ (ℝ≥0∞), and every infimum over policies ranges over the full class of history-dependent randomized policies. The $J^N$ and $r^N$ of (AC1) are real; the limits superior and inferior over $N$ in (AC2)–(AC4) and (WAC) are taken in EReal, so an unbounded sequence cannot produce a junk finite value. The equality $J(i)=\lim_N J^N$ is stated in EReal, which also asserts that $J(i)$ is finite. Quantities of $\Delta_N$ at states outside $S_N$ are junk values that affect only finitely many $N$ for each state.

A trivializing formalization is ruled out: $J^N$ and $r^N$ are the witnesses of (AC1), not free variables, the policies $e^N$ must realize the minimum in (8.1) for those witnesses, and the minimum average cost $J$ is an infimum over all policies, so the goal cannot be satisfied by choosing $J^*$ or the limit policy.

A complete development needs: the induced process law of a general policy; the average cost optimality inequality argument (Lemma 7.2.1); the finite-state average cost results of Chapter 6 (Propositions 6.4.1, 6.5.1, 6.6.3); a Fatou lemma for converging distributions (Proposition A.2.5); limit points of policy sequences (Proposition B.5); and, for the template results, the theory of $z$ standard chains and conformity (Appendix C.2–C.5). The Markov chain layer and the approximating sequence definitions are reusable beyond this mission. Contributions of any of these intermediate results as separate theorems are welcome.

Selected references

• L. I. Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems, Wiley Series in Probability and Statistics, John Wiley & Sons, 1999. https://doi.org/10.1002/9780470317037
• L. I. Sennott, "The computation of average optimal policies in denumerable state Markov decision chains", Advances in Applied Probability 29 (1997), 114–137 (cited as Sennott (1997a) in the book).
• L. I. Sennott, "On computing average cost optimal policies with application to routing to parallel queues", ZOR — Mathematical Methods of Operations Research 45 (1997), 45–62 (cited as Sennott (1997b) in the book).

Why average cost on finite state spaces

Controlled queues, inventories and communication links are run for a long time, and the quantity an operator usually cares about is the long-run average cost per period rather than a discounted total. The average cost criterion is harder to work with than the discounted one: its value is a $\limsup$ of Cesàro means, it is not given by a contraction, and for general (history dependent, randomized) policies the limit need not exist. Chapter 6 of L. I. Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems (Wiley, 1999) treats the case of a finite state space, where the strongest results hold: an average cost optimal policy exists, can be taken stationary, and can be obtained as a limit of discount optimal policies as the discount factor tends to one.

The results go back to D. Blackwell, "Discrete dynamic programming", Ann. Math. Statist. 33 (1962), who showed that for finite states and actions some stationary policy is discount optimal for all discount factors close to one. Such a policy is now called Blackwell optimal. Sennott's Chapter 6 derives average cost optimality of this policy and the multichain average cost optimality equation from it, in the notation used throughout the book.

Setting

A Markov decision chain (MDC) $\Delta$ has a countable state space $S$, a finite nonempty action set $A_i$ in each state $i$, nonnegative finite costs $C(i,a)$, and transition probabilities $P_{ij}(a)$ with $\sum_j P_{ij}(a) = 1$. A policy $\theta$ chooses the action at time $t$ from a distribution $\theta(\cdot \mid h_t)$ on $A_{i_t}$ that may depend on the whole history $h_t = (i_0,a_0,\ldots,i_t)$. A stationary policy $f$ always chooses a fixed action $f(i) \in A_i$ in state $i$.

With $X_t, A_t$ the state and action at time $t$ and $X_0 = i$, define

• the discounted cost $V_{\theta,\alpha}(i) = \sum_{t \ge 0} \alpha^t E_\theta[C(X_t,A_t)]$ for $0<\alpha<1$, and the discounted value function $V_\alpha(i) = \inf_\theta V_{\theta,\alpha}(i)$;
• the $n$ horizon cost $v_{\theta,n}(i) = \sum_{t=0}^{n-1} E_\theta[C(X_t,A_t)]$;
• the average cost $J_\theta(i) = \limsup_n v_{\theta,n}(i)/n$, its $\liminf$ version $J^*_\theta(i)$, and the minimum average cost $J(i) = \inf_\theta J_\theta(i)$.

All infima range over all general policies, and every quantity may equal $+\infty$. A policy is $\alpha$ discount optimal if $V_{\theta,\alpha} = V_\alpha$, and average cost optimal if $J_\theta = J$.

For a stationary policy $f$ on a finite state space, the induced Markov chain splits into positive recurrent classes $R_1,\ldots,R_K$ and transient states. With $p_k(i)$ the probability of reaching $R_k$ from $i$, distinguished states $z_k \in R_k$, and $W_\alpha(i) = \sum_k p_k(i) V_\alpha(z_k)$, the relative value function is $w_\alpha(i) = V_\alpha(i) - W_\alpha(i)$.

Formalization targets

Goal: Proposition 6.2.3

For an MDC with a finite state space there are $\alpha_0 \in (0,1)$ and one stationary policy $f$ such that $f$ is $\alpha$ discount optimal for every $\alpha \in (\alpha_0,1)$, $f$ is average cost optimal, and

$$J(i) = \lim_{\alpha\to 1^-} (1-\alpha) V_\alpha(i) = \lim_{n\to\infty} \frac{v_{f,n}(i)}{n}, \qquad i \in S.$$

Milestones

1. Proposition 4.5.3. For finite $S$ and stationary $e$, $\alpha \mapsto V_{e,\alpha}(i)$ is a finite, continuous, rational function on $(0,1)$.
2. Proposition 6.1.1. For every policy on a countable state space,

$$J^*_\theta(i) \le \liminf_{\alpha\to1^-}(1-\alpha)V_{\theta,\alpha}(i) \le \limsup_{\alpha\to1^-}(1-\alpha)V_{\theta,\alpha}(i) \le J_\theta(i),$$

with three equivalent conditions for equality. 3. Proposition 6.2.2. For finite $S$ and stationary $e$, $J_e(i) = \lim_{\alpha\to1^-}(1-\alpha)V_{e,\alpha}(i) = \lim_n v_{e,n}(i)/n$. 4. Proposition 4.5.1, Proposition 4.5.4, Corollary 4.5.5. The power series structure of $V_{\theta,\alpha}$ in $\alpha$; monotonicity and left continuity of $V_\alpha$; continuity under bounded costs. 5. Theorem 6.3.1. For the policy $f$ of the goal, $\lim_{\alpha \to 1^-} w_\alpha(i) = w(i)$ exists, and

$$J(i) + w(i) = C(i,f) + \sum_j P_{ij}(f) w(j) \ \ge\ \min_{a} \Big\{C(i,a) + \sum_j P_{ij}(a) w(j)\Big\},$$

together with the limit identities (i)–(iii) and the optimality criterion (v). 6. Proposition 6.3.3. $V_\alpha(i) = J(i)/(1-\alpha) + w^*(i) + \varepsilon_\alpha(i)$ with $\varepsilon_\alpha(i) \to 0$ as $\alpha \to 1^-$.

Significance

The goal says that on a finite state space nothing is gained by randomizing or by remembering the past when minimizing average cost, and that the minimum average cost is the vanishing-discount limit of the discounted value function. This justifies computing average cost optimal policies through discounted problems and value iteration, the route taken in the rest of Chapter 6 and, via approximating sequences, for countable state spaces in Chapters 7 and 8. Theorem 6.3.1 supplies an optimality equation without any unichain or communication assumption. The book's Example 6.3.2 shows that the inequality in that equation can be strict, and that a stationary policy attaining the minimum need not be optimal.

The results are classical and proved in the book. No machine-checked version of them is known to exist. The platform has average-reward results for unichain finite MDPs with Markov policies (the Puterman series) and an average-cost optimality equation under recurrence assumptions (the Bertsekas series). Neither covers existence of a Blackwell optimal policy against the class of all history dependent randomized policies, or the multichain equation. A formal development also yields reusable infrastructure: the law of a controlled process under a general policy, first passage quantities of finite chains, and the Abelian inequality between Abel and Cesàro means of a nonnegative sequence.

Difficulty

The obvious argument picks, for each $\alpha$, a stationary discount optimal policy $f_\alpha$ and lets $\alpha \to 1$. Finiteness of the set of stationary policies gives one policy that is optimal along some sequence $\alpha_n \to 1$, but not on an interval. Excluding infinite switching between two policies requires the analytic structure of $\alpha \mapsto V_{f,\alpha}(i)$ (Proposition 4.5.3), which in turn rests on matrix inversion of $I - \alpha P$. Passing from the discounted criterion to the average one requires an Abelian inequality for nonnegative series whose terms may be infinite (Proposition 6.1.1), and comparison against general policies rules out any argument that works only within stationary or Markov policies. For Theorem 6.3.1 the difficulty is the multichain structure: the relative value function has to be assembled class by class from first passage times and costs, and its limit must be identified.

Formalization scope

• States form a type S; [Countable S] for Section 4.5 and Proposition 6.1.1, [Fintype S] from Section 6.2 on, as in the book. Actions form a type Act with A i : Finset Act nonempty. Costs are in ℝ≥0, transition probabilities in ℝ≥0∞.
• A general policy is a function of the list of past state-action pairs (most recent first) and the current state, giving a distribution on A i. Stationary policies embed as degenerate policies. The law of the process is built from this data, and every infimum ranges over all general policies.
• $V_{\theta,\alpha}$, $V_\alpha$, $v_{\theta,n}$, $J_\theta$, $J^*_\theta$, $J$ are in ℝ≥0∞, so $+\infty$ is represented. $\alpha \to 1^-$ is the filter 𝓝[<] 1. On a finite state space these quantities are finite. The real valued objects of Section 6.3 ($w_\alpha$, $w$, $w^*$, equation (6.6)) are therefore formed with toReal, and this switch from ℝ≥0∞ to ℝ happens only in Theorem 6.3.1 and Proposition 6.3.3.
• The objects of Section 6.3 ($p_k$, $m_{i|k}$, $c_{i|k}$, $\pi_s$, $W_\alpha$) are defined from $f$. The distinguished states are a hypothesis quantified over.
• A trivializing formalization would take the infimum over stationary policies only, let the optimal policy depend on $\alpha$, or state rationality as an equation p/q without requiring $q \ne 0$. Each is excluded here: $J$ and $V_\alpha$ are infima over all general policies, one pair $(\alpha_0,f)$ is quantified before all $\alpha$, and the denominator is required to be nonzero on $(0,1)$.

Useful infrastructure includes rational functions of one real variable and their finitely many sign changes, the resolvent $(I-\alpha P)^{-1}$ of a stochastic matrix, the Abelian inequality for $[0,\infty]$-valued sequences, and renewal-reward identities for finite chains. Contributions of general lemmas on these topics are welcome, as are proofs of individual milestones.

Selected references

• L. I. Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems, Wiley, 1999. https://doi.org/10.1002/9780470317037
• D. Blackwell, "Discrete dynamic programming", Annals of Mathematical Statistics 33 (1962), 719–726. https://doi.org/10.1214/aoms/1177704593
• M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley, 1994. https://doi.org/10.1002/9780470316887

Motivation

Control problems for queueing systems (admission control, routing, service rate selection, inventory replenishment) are naturally modelled as Markov decision chains with a countable state space, such as the number of customers in a buffer, and with costs that grow without bound in the state, such as holding costs proportional to queue length. The expected discounted cost criterion is the first infinite horizon criterion applied to such models, and it is also the tool through which the average cost criterion is treated later in the same book (Chapters 6–8 of Sennott's text reach average cost optimal policies through limits of discounted problems as the discount factor tends to one).

Classical treatments of discounted dynamic programming assume bounded costs, under which the dynamic programming operator is a contraction and has a unique bounded fixed point. That assumption fails for queueing models. This mission formalizes Chapter 4, Sections 4.1–4.4, of L. I. Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems (Wiley, 1999), which develops the discounted theory for nonnegative, possibly unbounded costs, where value functions may be infinite.

Timeline of the underlying theory:

• 1965. Blackwell (Ann. Math. Statist. 36) establishes the discounted theory with bounded rewards.
• 1966. Strauch (Ann. Math. Statist. 37) treats "negative" dynamic programming, the case of nonpositive rewards (equivalently nonnegative costs), with no boundedness assumption.
• 1977–1978. Bertsekas (SIAM J. Control Optim. 15) and Bertsekas and Shreve (Stochastic Optimal Control: The Discrete-Time Case) give the abstract monotone-mapping framework covering both cases.
• 1999. Sennott's text states the countable-state, finite-action, nonnegative-cost discounted theory in the form used for queueing control, with general history-dependent randomized policies.

Setting

A Markov decision chain $\Delta$ has a countable state space $S$; for each state $i$ a finite nonempty action set $A_i$; for each $a \in A_i$ a nonnegative finite cost $C(i,a)$ and a probability distribution $(P_{ij}(a))_{j \in S}$ of the next state. A policy $\theta$ chooses the action at time $n$ at random from a distribution $\theta(\cdot \mid h_n)$ on $A_{i_n}$ that may depend on the entire history $h_n = (i_0, a_0, \dots, a_{n-1}, i_n)$. A stationary policy $f$ always chooses $f(i) \in A_i$ in state $i$; for it one writes $C(i,f) = C(i,f(i))$ and $P_{ij}(f) = P_{ij}(f(i))$.

Fix a discount factor $\alpha \in (0,1)$. For an initial state $i$ and a policy $\theta$, the $n$-horizon cost with terminal cost zero and the infinite horizon discounted cost are

$$v_{\theta,\alpha,n}(i) = \sum_{t=0}^{n-1} \alpha^t E_\theta[C(X_t,A_t) \mid X_0 = i], \qquad V_{\theta,\alpha}(i) = \sum_{t=0}^{\infty} \alpha^t E_\theta[C(X_t,A_t) \mid X_0 = i],$$

and the value functions are $v_{\alpha,n}(i) = \inf_\theta v_{\theta,\alpha,n}(i)$ and $V_\alpha(i) = \inf_\theta V_{\theta,\alpha}(i)$, infima over all policies. All of these lie in $[0,\infty]$. A policy is discount optimal if $V_{\theta,\alpha} = V_\alpha$. The discount optimality equation is

$$W(i) = \min_{a \in A_i} \Big\{ C(i,a) + \alpha \sum_j P_{ij}(a) W(j) \Big\}, \qquad i \in S. \tag{4.9}$$

With $W = V_\alpha$, $B_i(\alpha)$ denotes the set of actions attaining the minimum at $i$.

Formalization targets

Goal: Theorem 4.1.4

$V_\alpha$ solves (4.9); every $W : S \to [0,\infty]$ solving (4.9) satisfies $V_\alpha \le W$; and every stationary policy $f_\alpha$ with

$$C(i,f_\alpha) + \alpha \sum_j P_{ij}(f_\alpha) V_\alpha(j) = \min_a \Big\{ C(i,a) + \alpha \sum_j P_{ij}(a) V_\alpha(j) \Big\} \quad \text{for all } i$$

is discount optimal. No boundedness of costs and no finiteness of $V_\alpha$ is assumed.

Milestones

In attack order: Lemma 4.1.1 ($v_{\theta,\alpha,n} \uparrow V_{\theta,\alpha}$); Proposition 4.1.2 (a supersolution of the one-policy equation dominates $v_{e,\alpha,n} + \alpha^n E_e[W(X_n)]$ and $V_{e,\alpha}$); Corollary 4.1.3 (a supersolution of the optimality inequality dominates $V_{f,\alpha} \ge V_\alpha$); then, beyond the goal, Corollary 4.1.5 ($\alpha^n E_{f_\alpha}[V_\alpha(X_n) \mid X_0 = i] \to 0$ where $V_\alpha(i) < \infty$), Proposition 4.2.2 and Corollary 4.2.4 (conditions under which a solution of (4.9) equals $V_\alpha$), Proposition 4.3.1 ($v_{\alpha,n} \uparrow V_\alpha$, and limit points of finite horizon optimal stationary policies are discount optimal) and Proposition 4.4.1 (optimal policies are exactly those concentrated on the sets $B_{i}(\alpha)$ along histories of positive probability).

Significance

Theorem 4.1.4 is the foundation for everything in the book that concerns discounted costs: it produces an optimal stationary deterministic policy, identifies $V_\alpha$ among the many solutions of (4.9) (Example 4.2.1 of the book gives a one-parameter family of finite solutions), and underlies value iteration (Proposition 4.3.1) and the approximating-sequence method of Sections 4.6–4.7. The average cost results of Chapters 6–8 are proved from it by letting $\alpha \to 1$. Proposition 4.4.1 describes the full set of optimal policies, including randomized and history-dependent ones.

These are known results with published proofs. The contribution of this mission is a machine-checked development of the discounted theory for countable state spaces with unbounded costs and infinite values, over the general policy class. Related statements on the platform (the monotone-mapping propositions of Bertsekas 1977 in the MonotoneDP missions, and bounded-cost or finite-state discounted results) use different models and are open; no machine-checked proof of the present statements is known to this mission.

Difficulty

The contraction argument that settles the bounded case is unavailable: with unbounded costs the operator in (4.9) has many fixed points, and $V_\alpha$ can equal $+\infty$ at some states, so neither uniqueness of fixed points nor subtraction of values is available. The optimality equation compares the infimum over all history-dependent randomized policies with a one-step minimum, so the general policy class and the law of the process under it must be handled directly; restricting attention to Markov or stationary policies begs the question. Every limit exchange (monotone limits of finite horizon costs, the passage to limit points of policies in Proposition 4.3.1) takes place in $[0,\infty]$, where finite-valued arguments do not transfer verbatim.

Formalization scope

The Lean development lives in the namespace SennottDP.Discounted. Conventions:

• The state space is a type S with [Countable S]; actions form a type Act and A i : Finset Act is nonempty. Costs are ℝ≥0; transition probabilities are ℝ≥0∞ with ∑' j, P i a j = 1 for a ∈ A i.
• A history at time $n$ is a pair Fin (n+1) → S, Fin n → Act; a policy assigns to every history a distribution on the action set of its last state. The probability of a history is the product of the policy and transition probabilities; expectations are ℝ≥0∞ sums over histories, so no integrability conditions arise.
• All values ($v_{\theta,\alpha,n}$, $V_{\theta,\alpha}$, $v_{\alpha,n}$, $V_\alpha$, and the competing solutions $W$) are ℝ≥0∞-valued; $0 \cdot \infty = 0$. The discount factor is α : ℝ≥0 with 0 < α and α < 1. Terminal costs are zero.
• $V_\alpha$ and $v_{\alpha,n}$ are infima over the type of all general policies. Defining them over stationary policies only would make the optimality of $f_\alpha$ a tautology; that formalization is ruled out.
• Proposition 4.4.1: the book states the equivalence without a finiteness assumption, but its necessity argument needs $V_\alpha < \infty$, and necessity fails otherwise. Sufficiency is stated in general and necessity under $V_\alpha < \infty$ everywhere.

Useful infrastructure, reusable by the later missions of this series (approximating sequences, average cost): the shift of a general policy after its first step, the Chapman–Kolmogorov identity for the history law, and the computation $E_f[W(X_{n+1})] = E_f[\sum_j P_{X_n j}(f) W(j)]$ for stationary policies. Contributions of such lemmas, and proofs of any milestone, are welcome.

Selected references

• L. I. Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems, Wiley Series in Probability and Statistics, John Wiley & Sons, 1999, Chapter 4. https://doi.org/10.1002/9780470317037
• D. Blackwell, Discounted dynamic programming, Annals of Mathematical Statistics 36 (1965), 226–235. https://doi.org/10.1214/aoms/1177700285
• R. E. Strauch, Negative dynamic programming, Annals of Mathematical Statistics 37 (1966), 871–890. https://doi.org/10.1214/aoms/1177699369
• D. P. Bertsekas, Monotone mappings with application in dynamic programming, SIAM Journal on Control and Optimization 15 (1977), 438–464. https://doi.org/10.1137/0315031
• D. P. Bertsekas and S. E. Shreve, Stochastic Optimal Control: The Discrete-Time Case, Academic Press, 1978.
• M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley, 1994. https://doi.org/10.1002/9780470316887