3 Properties of value functions

3.1 Review

In the previous lecture we derived dynamic programming for state space models and noted that, for computation and for the approximation results that follow, it is convenient to work with the controlled Markov chain representation. We briefly recall the resulting recursions.

Let $\ALPHABET M = \langle \ALPHABET S, \ALPHABET A, P, c, T \rangle$ denote an MDP (equivalently, a controlled Markov chain), with state space $\ALPHABET S$, action space $\ALPHABET A$, controlled transition kernels $P = (P_1, \dots, P_T)$, per-step costs $c = (c_1, \dots, c_T)$, and horizon $T$. For simplicity we take $c_t \colon \ALPHABET S \times \ALPHABET A \to \reals$; if the primitive cost depends on the next state as well, the same formulas apply with $c_t(s,a)$ interpreted as the conditional expectation of that cost given $(S_t,A_t)=(s,a)$.

We write $\ALPHABET V$ for the space of value functions and $\ALPHABET Q$ for the space of action-value functions.

3.1.1 Policy optimization

Dynamic programming is a recursive algorith which computes $V^\star_t \in \ALPHABET V$ and $Q^\star_t \in \ALPHABET Q$ as follows:

Initialize $V^\star_{T+1}(s) \equiv 0$. For $t = T, T-1, \dots, 1$, \[\begin{align} Q^\star_t(s,a) &= c_t(s,a) + \sum_{s' \in \ALPHABET S} P_t(s' \mid s,a)\, V^\star_{t+1}(s'), \\ V^\star_t(s) &= \min_{a \in \ALPHABET A} Q^\star_t(s,a), \\ π^\star_t(s) &\in \arg\min_{a \in \ALPHABET A} Q^\star_t(s,a). \end{align}\] The policy $π^\star = (π^\star_1, \dots, π^\star_T)$ obtained from this recursion is optimal, and $V^\star_t(s)$ is the optimal cost-to-go from state $s$ at time $t$.

3.1.2 Policy evaluation

Dynamic programming can also be used to evaluate the performance of a Markov policy $π = (π_1, \dots, π_T)$ by recursively computing $V^π \in \ALPHABET V$ and $Q^π \in \ALPHABET Q$ as follows:

Initialize $V^π_{T+1}(s) \equiv 0$. For $t = T, T-1, \dots, 1$, \[\begin{align} Q^π_t(s,a) &= c_t(s,a) + \sum_{s' \in \ALPHABET S} P_t(s' \mid s,a)\, V^π_{t+1}(s'), \\ V^π_t(s) &= Q^π_t\bigl(s, π_t(s)\bigr). \end{align}\]

Then, \[ J(π) = \EXP\bigl[V^π_1(S_1)\bigr] \] and by a backward induction argument we can show that \[ J(π^\star) \le J(π), \quad \forall π \in Π. \] Therefore, the policy $π^\star$ obtained by dynamic programming is optimal.

3.2 Operator theoretic notation

It is convenient to package the recursions above using a compact notation. The standard way to write these is using what are called Bellman operators. I find that the Bellman operators are a bit opaque and a slightly different (but unconventional) notation is much more transparent. We discuss both these notations below.

3.2.1 Bellman operators

For any policy $π \in Π$, define the policy Bellman operator $\BELLMAN^π_t \colon \ALPHABET V \to \ALPHABET V$ as follows: for any $v \in \ALPHABET V$, \[ [\BELLMAN^π_t v](s) = c_t(s, π(s)) + \sum_{s' \in \ALPHABET S} P_t(s'|s, π(s)) v(s'). \]
Define the optimality Bellman operator $\BELLMAN^\star_t \colon \ALPHABET V \to \ALPHABET V$ as follows: for any $v \in \ALPHABET V$, \[ [\BELLMAN^\star_t v](s) = \min_{a \in \ALPHABET A} \biggl\{ c_t(s, a) + \sum_{s' \in \ALPHABET S} P_t(s'|s, a) v(s') \biggr\}. \]

Then the dynamic programming decomposition can be written succinctly as: \[ V^\star_{T+1} = 0, \quad\text{and}\quad V^\star_t = \BELLMAN^\star_t V^\star_{t+1}, \quad \forall t \in \{T,\dots,1\}. \] Or, pictorially: \[ 0 ≡ V^\star_{T+1} \xrightarrow{\BELLMAN^\star} V^\star_T \xrightarrow{\BELLMAN^\star} V^\star_{T-1} \cdots \xrightarrow{\BELLMAN^\star} V^\star_1. \] Moreover, a policy $π^\star = (π^\star_1, \dots, π^\star_T) \in Π$ is optimal if and only if $\BELLMAN^\star_t V^\star_{t+1} = \BELLMAN^{π^\star}_t V^\star_{t+1}$ for all $t$.

Similarly, for a policy $π ∈ Π$, the policy evaluation dynamic program can be written as: \[ 0 ≡ V^π_{T+1} \xrightarrow{\BELLMAN^π} V^π_T \xrightarrow{\BELLMAN^π} V^π_{T-1} \cdots \xrightarrow{\BELLMAN^π} V^π_1. \]

3.2.2 Factorization via environment and action selection operators

It is useful to factor each Bellman operator into a model-dependent piece and a model-independent piece that only selects or optimizes over actions. (This factorization is not a commonly used notation in the literature.)

Define the operator $\ENV_t \colon \ALPHABET V \to \ALPHABET Q$ as the environment operator: for any $v \in \ALPHABET V$, \[ [\ENV_t v](s,a) = c_t(s,a) + \sum_{s' \in \ALPHABET S} P_t(s'|s,a) v(s'). \]
For any $π \in Π$, define the action selection operator $\ALPHABET T^π$ as follows: for any $q \in \ALPHABET Q$, \[ [\ALPHABET T^π q](s) = q(s, π(s)) \quad\text{or for stochastic $π$ } [\ALPHABET T^π q](s) = \sum_{a \in \ALPHABET A} π(a | s)q(s, a). \]
Define the optimality action selection operator $\ALPHABET T^\star$ as follows: for any $q \in \ALPHABET Q$, \[ [\ALPHABET T^\star q](s) = \min_{a \in \ALPHABET A} q(s, a). \]
Define $\GREEDY \colon \ALPHABET Q \rightrightarrows Π$ as the greedy policy: given a $q \in \ALPHABET Q$, $π \in \GREEDY q$ means that $π(s) \in \arg\min_{a \in \ALPHABET A} q(s,a)$.

Observe that \[ \BELLMAN^π_t = \ALPHABET T^π \circ \ENV_t, \quad \text{and}\quad \BELLMAN^\star_t = \ALPHABET T^\star \circ \ENV_t. \]

The dynamic programming recursion can therefore be written with action-value functions made explicit: \[ V^\star_{T+1} = 0, \quad\text{and}\quad Q^\star_t = \ENV_t V^\star_{t+1}, \quad V^\star_t = \ALPHABET T^\star Q^\star_t, \quad \forall t \in \{T,\dots,1\}. \] Or, pictorially: \[ 0 ≡ V^\star_{T+1} \xrightarrow{\ENV_T} Q^\star_T \xrightarrow{\ALPHABET T^\star} V^\star_T \xrightarrow{\ENV_{T-1}} Q^\star_{T-1} \cdots \xrightarrow{\ALPHABET T^\star} V^\star_1. \] Moreover, a policy $π^\star = (π^\star_1, \dots, π^\star_T) \in Π$ is optimal if and only if $π^\star_t \in \GREEDY Q^\star_t$. An implication is that $\ALPHABET T^\star Q^\star_{t} = \ALPHABET T^{π^\star} Q^\star_t$.

Similarly, for a policy $π ∈ Π$, \[ 0 ≡ V^π_{T+1} \xrightarrow{\ENV_T} Q^π_T \xrightarrow{\ALPHABET T^π} V^π_T \xrightarrow{\ENV_{T-1}} Q^π_{T-1} \cdots \xrightarrow{\ALPHABET T^π} V^π_1. \]

The environment operator $\ENV_t$ depends on $(P_t,c_t)$; the action selection operators $\ALPHABET T^π$ and $\ALPHABET T^\star$ do not.

3.3 Motivation for model approximation

The following example motivates why approximation needs quantitative properties of value functions.

Example 3.1 (Internet of things) Assume that $\ALPHABET S = [-B, B]$, $\ALPHABET A = \{0, 1\}$ and the dynamics are given by \[ S_{t+1} = \begin{cases} [S_t + W_t]_{-B}^B, & \text{if }A_t = 0 \\ [W_t]_{-B}^B, & \text{if }A_t = 1 \end{cases} \] where $[x]_{-B}^B = \text{clip}(x,-B,B)$. We assume that $\{W_t\}_{t \ge 1}$ is an i.i.d. process with known distribution $F_W$. The per-step cost is given by \[ c(s,a) = \lambda a + (1-a)s^2. \] Find the policy that minimizes the expected total cost over a finite horizon.

As usual, the dynamic program for Example 3.1 is given by $V_{T+1}(s) = 0$ for all $s \in \ALPHABET S$ and for $T \in \{T, \dots, 1\}$, \[ V_{t}(s) = \min\biggl\{ s^2 + \int V_{t+1}([s + W]_{-B}^B) F_W(dW), λ + V_{t+1}([W]_{-B}^B) F_W(dW) \biggr\}, \quad \forall s \in \ALPHABET S \]

Since the DP is continuous, it cannot be solved exactly apart from some special cases. For numerical solution, we need some form of approximation that needs to tackle two conceptual difficulties:

Solve the DP recursion for all $s \in \ALPHABET S$
Compute the expectation with respect to a continuous random variable.

For now, we focus on the first difficulty. In low dimensions, the simplest approximation scheme is state discretization or quantization: partition the state space $\ALPHABET S$ into a partition $\{\ALPHABET C_1, \dots, \ALPHABET C_n\}$ with $n$ “cells”, where each cell $\ALPHABET C_i$ is represented by a single element $\hat s_i$. This gives a finite state space $\hat {\ALPHABET S} \coloneqq \{ \hat s_1, \dots, \hat s_n \}$.

For example, in Example 3.1 we can define a partition using boundary points \[ -B = b_1 < b_1 < \cdots < b_{n+1} = B \] and set the representative points as $\hat s_i = (b_i + b_{i+1})/2$, $i \in \{1, \dots, n\}$.

The next step is to define a quantized model with dynamics $\hat P$ and per-step cost $\hat c$ on $\hat {\ALPHABET S} × \ALPHABET A$. The simplest way to define such a quantized model is: \[\begin{align*} \hat c(\hat s, a) &= c(s,a) \\ \hat P(\hat s_j | \hat s_i, a) &= P(\ALPHABET C_j | \hat s_i, a) = \int_{\ALPHABET C_j} P(ds'|\hat s_i, a). \end{align*}\]

Let $\{ (\hat V_t, \hat π_t) \}_{t=1}^T$ denote the solution of the DP for the model $(\hat P, \hat c)$. Note that $\hat π_t$ is a policy on the state space $\hat {\ALPHABET S}$. To obtain a policy defined on $\ALPHABET S$, define the quantization function $φ \colon \ALPHABET S \to \hat {\ALPHABET S}$ to be a function which maps any state $s$ to the representative of the cell containing it. Define $\bar V_t = \hat V_t \circ φ$ and $\bar π_t = \hat π \circ φ$, i.e., \[ \bar V_t(s) = \hat V_t(φ(s)) \quad\text{and}\quad \bar π_t(s) = \hat π(φ(s)). \] $\{(\bar V_t, \bar π_t) \}_{t=1}^T$ may be viewed as an approximate value function and approximate policy for the model $(P,c)$.

As an illustration, we solve Example 3.1 using such a quantization scheme.

module IOT_quantization
  using Distributions, OffsetArrays, LinearAlgebra

  function solve(; λ=100.0, B=10.0, σ=0.5, T=20, n=51)
    dist_W = Normal(0, σ)
    A = 0:1

    boundaries = range(-B, B, length=n+1)
    S_hat = [(boundaries[i] + boundaries[i+1])/2 for i in 1:n]

    c(s, a) = λ * a + (1 - a) * s^2
    P_hat = OffsetArray(zeros(n, n, length(A)), 1:n, 1:n, A)
    c_hat = OffsetArray(zeros(n, length(A)), 1:n, A)

    for a in A
      for i in 1:n
        si = S_hat[i]
        c_hat[i, a] = c(si, a)

        s_post = (a == 0) ? si : 0.0

        for j in 1:n
            P_hat[i, j, a] = cdf(dist_W, boundaries[j+1] - s_post) - cdf(dist_W, boundaries[j] - s_post)
        end

        P_hat[i, 1, a] += cdf(dist_W, boundaries[1] - s_post)
        P_hat[i, n, a] += 1.0 - cdf(dist_W, boundaries[end] - s_post)
      end
    end

    V = [zeros(n) for t in 1:T+1]
    π = [zeros(Int, n) for t in 1:T]

    for t in T:-1:1
      for i in 1:n
        Q0 = c_hat[i, 0] + dot(P_hat[i, :, 0], V[t+1])
        Q1 = c_hat[i, 1] + dot(P_hat[i, :, 1], V[t+1])

        (V[t][i], π[t][i]) = (Q0 <= Q1) ? (Q0,0) : (Q1,1)
      end
    end

    return V, π, S_hat
  end
end

We solve this model with $n = 2^k + 1$, for different values of $k$. This sequence is chosen so that the number of quantization in $(0,B]$ doubles every iteration. The plots

Observe that the distance between the points is $Δ = 2B/2^{k}$, so for $k = 10$, we have $Δ \approx 0.0195$, and the approximation looks almost continuous. Thus, we expect the corresponding approximate value function and policy to be close to the optimal value function and policy.

viewof iot_k = Object.assign(Inputs.range([5,10], {label: "k", step: 1, value: 6}), {style: '--label-width:20px'})
iot_n = 2**iot_k + 1

Plot.plot({
  grid: true,
  x: { label: "State s" },
  y: { label: "Value", domain: [0, 175] },
  marks: [
    Plot.ruleX([0]),
    Plot.ruleY([0]),
    Plot.line(iot_df.filter(d => d.n === iot_n), {x: "s", y: "value", curve: "step"})
  ]
})
Plot.plot({
  grid: true,
  x: { label: "State s" },
  y: { label: "Action", ticks: [0, 1] },
  marks: [
    Plot.ruleX([0]),
    Plot.ruleY([0]),
    Plot.line(iot_df.filter(d => d.n === iot_n), {x: "s", y: "policy", curve: "step"})
  ]
})

(a) Approx value function

(b) Approx policy

Figure 3.1: Value function $V_1(s)$ and optimal policy $π_1(s)$ at $t=1$ (number of cells $n$)

We are interested in understanding if we can quantify the quality of the approximation without knowing the exact solution. Model approximation changes transition laws (and possibly costs), so the first question is: how much can an expectation change when the underlying measure changes? That question leads to integral probability metrics (IPMs). Once the right metrics are in place, the remaining task is to control how irregular the value functions are (their span and Lipschitz constants), which is what we develop in the rest of this lecture.

3.4 Changing measures and integral probability metrics

Fix a finite state space $\ALPHABET S$ and a function $v \colon \ALPHABET S \to \reals$. If $μ$ and $ν$ are two probability distributions on $\ALPHABET S$, we want to bound \[ \ABS{\sum_{s \in \ALPHABET S} μ(s) v(s) - \sum_{s \in \ALPHABET S} ν(s) v(s)}. \] In model approximation, $μ$ and $ν$ are typically one-step transition kernels $P_t(\cdot \mid s,a)$ and $\hat P_t(\cdot \mid s,a)$, and $v$ is a continuation value. The same pattern appears whenever one replaces a true expectation by an approximate one. (On continuous spaces the same bounds hold with integrals in place of sums; we keep the finite-sum notation in this lecture.)

3.4.1 A simple $\ell_1$ bound

\[\begin{align*} \ABS{\sum_{s \in \ALPHABET S} μ(s) v(s) - \sum_{s \in \ALPHABET S} ν(s) v(s)} &= \ABS{\sum_{s \in \ALPHABET S} \bigl(μ(s)-ν(s)\bigr) v(s)} \\ &\le \sum_{s \in \ALPHABET S} \ABS{μ(s)-ν(s)}\, \ABS{v(s)} \\ &\le \NORM{μ-ν}_{1}\, \NORM{v}_{∞}, \end{align*}\] where $\NORM{μ-ν}_{1} = \sum_{s} \ABS{μ(s)-ν(s)}$ and $\NORM{v}_{∞} = \sup_{s} \ABS{v(s)}$.

Thus the change in expectation is controlled by an $\ell_1$ distance between distributions times the size of $v$ in the sup-norm. The bound is loose in one respect: adding a constant to $v$ does not change $\sum_s μ(s)v(s) - \sum_s ν(s)v(s)$, but it can inflate $\NORM{v}_{∞}$.

Define the span of $v$ by \[ \SPAN(v) \coloneqq \max_{s \in \ALPHABET S} v(s) - \min_{s \in \ALPHABET S} v(s). \] Subtracting a constant so that $\max(v) = -\min(v)$ gives $\NORM{v}_{∞} = \tfrac12 \SPAN(v)$, and therefore :::{#prp-TV-span-bound} #### Total-variation / span bound For any probability distributions $μ,ν$ on $\ALPHABET S$ and any $v \colon \ALPHABET S \to \reals$, \[ \ABS{\sum_{s} μ(s) v(s) - \sum_{s} ν(s) v(s)} \le \NORM{μ-ν}_{1}\, \tfrac12 \SPAN(v). \] ::: We write $d_{\mathrm{TV}}(μ,ν) \coloneqq \NORM{μ-ν}_{1}$ for this $\ell_1$ distance and call it total variation.¹

3.5 Wasserstein distance

Total variation treats every disagreement between $μ$ and $ν$ as equally severe. If two distributions put their mass on nearby states, the expectations of a slowly varying $v$ should change only a little, yet $d_{\mathrm{TV}}$ may still be large (even equal to $2$ when the supports are disjoint). In continuous or geometrically structured state spaces, that makes $d_{\mathrm{TV}}$ a pessimistic modelling distance: quantization, small location shifts, and other “nearby” perturbations look as bad as completely unrelated laws.

When the state space is a metric space with metric $d_{\ALPHABET S}$, a more geometric alternative is the Wasserstein distance $W_1$. Informally, $W_1(μ,ν)$ is the minimum cost of transporting the mass of $μ$ onto $ν$ when moving a unit of mass from $s$ to $\tilde s$ costs $d_{\ALPHABET S}(s,\tilde s)$. Discrepancies between nearby states are cheap; discrepancies between far-away states are expensive.

For our purposes, the following dual characterization of $W_1$ is sufficient: \[ W_1(μ,ν) = \sup\biggl\{ \ABS{\sum_{s} μ(s) v(s) - \sum_{s} ν(s) v(s)} : \operatorname{Lip}(v) \le 1 \biggr\}, \] where the Lipschitz constant of $v \colon \ALPHABET S \to \reals$ is \[ \operatorname{Lip}(v) = \sup_{s \ne \tilde s} \frac{\ABS{v(s)-v(\tilde s)}}{d_{\ALPHABET S}(s,\tilde s)} \in [0,∞]. \] The function $v$ is called Lipschitz continuous if $\operatorname{Lip}(v) < ∞$.

Proposition 3.1 (Kantorovich–Rubinstein inequality) For any Lipschitz $v \colon \ALPHABET S \to \reals$ and any probability distributions $μ,ν$ on $\ALPHABET S$, \[ \ABS{\sum_{s} μ(s) v(s) - \sum_{s} ν(s) v(s)} \le \operatorname{Lip}(v)\, W_1(μ,ν). \]

This follows immediately from the dual definition of $W_1$. If $\operatorname{Lip}(v)=0$, then $v$ is constant and both sides vanish. If $L \coloneqq \operatorname{Lip}(v) \in (0,∞)$, then $v/L$ is $1$-Lipschitz, so \[ \ABS{\sum_{s} μ(s) \frac{v(s)}{L} - \sum_{s} ν(s) \frac{v(s)}{L}} \le W_1(μ,ν), \] and multiplying through by $L$ yields Proposition 3.1.

Remark

In the literature the same inequality is usually called Kantorovich–Rubinstein duality when one starts from the primal (optimal-transport / coupling) definition of $W_1$ and proves that it coincides with the Lip dual above. Here we take the dual characterization as the definition of $W_1$, so Proposition 3.1 is just scaling, not a duality theorem.

This is the Wasserstein counterpart of the span bound above: the “size” of $v$ is now measured by $\operatorname{Lip}(v)$ rather than by $\SPAN(v)$, and the distance on distributions respects geometry.

3.5.1 Integral probability metrics

Total variation and Wasserstein are instances of a single dual template. Let $\def\F{\mathfrak{F}}\F$ be a class of real-valued test functions on $\ALPHABET S$. The associated integral probability metric (IPM) is \[ d_{\F}(μ,ν) = \sup_{f \in \F} \ABS{\sum_{s} μ(s) f(s) - \sum_{s} ν(s) f(s)}. \] For a general $v$, write $ρ_{\F}(v)$ for the Minkowski gauge of $\F$ (the smallest $r>0$ such that $v/r \in \F$, when $\F$ is a suitable unit ball). Then \[ \ABS{\sum_{s} μ(s) v(s) - \sum_{s} ν(s) v(s)} \le ρ_{\F}(v)\, d_{\F}(μ,ν). \] In particular:

If $\F = \{ f : \tfrac12 \SPAN(f) \le 1 \}$, then $d_{\F} = d_{\mathrm{TV}}$ and $ρ_{\F}(v) = \tfrac12 \SPAN(v)$.
If $\F = \{ f : \operatorname{Lip}(f) \le 1 \}$, then $d_{\F} = W_1$ and $ρ_{\F}(v) = \operatorname{Lip}(v)$, which is Proposition 3.1.

Other IPMs (maximum mean discrepancy, bounded-Lipschitz distance, etc.) arise from other choices of $\F$. In this course we focus on total variation and Wasserstein distance. More background is in the IPM notes.

In the remainder of this lecture, we establish properties of the span and of the Lipschitz constants of value functions.

3.6 Span semi-norm

We have already used $\SPAN(v) = \sup v - \inf v$. We now record its basic properties systematically.

$\SPAN(v) \ge 0$ for all $v \in \reals^n$.
$\SPAN(v + w) \le \SPAN(v) + \SPAN(w)$ for all $v, w \in \reals^n$.
$\SPAN(m v) = |m| \SPAN(v)$ for all $v \in \reals^n$ and $m \in \reals$.
$\SPAN(v + m \mathbf{1}) = \SPAN(v)$ for all $m \in \reals$.
$\SPAN(v) = \SPAN(-v)$.
$\SPAN(v) \le 2\NORM{v}_{∞}$.

Properties 1–3 imply that $\SPAN$ is a semi-norm. It is not a norm because of property 4: $\SPAN(v) = 0$ does not imply $v = 0$. If $\SPAN(v) = 0$, then $v = m \mathbf{1}$ for some scalar $m$.

A basic result for our analysis is the following. (Here $P$ is a row-stochastic matrix, as arises from a controlled transition kernel.)

Proposition 3.2 (Span contraction for stochastic matrices) Let $v \in \reals^n$ and let $P$ be a row-stochastic matrix of compatible dimensions. Then \[ \SPAN(P v) \le λ(P) \SPAN(v), \] where \[\begin{equation} \label{eq:span-matrix} λ(P) = \frac12 \max_{s, s' \in \ALPHABET S} \sum_{z \in \ALPHABET S} \ABS{P_{sz} - P_{s'z}} = \frac12 \max_{s, s' \in \ALPHABET S} d_{\mathrm{TV}}\bigl(P_{s\cdot},\, P_{s'\cdot}\bigr). \end{equation}\] Furthermore, $λ(P) \in [0, 1]$ and there exists a $v \in \reals^n$ such that $\SPAN(Pv) = λ(P) \SPAN(v)$.

Proof

For any $v \in \reals^n$, \[\begin{align*} \SPAN(Pv) &= \max_{s, s' \in \ALPHABET S} \Biggl( \sum_{z \in \ALPHABET S} P_{sz} v_z - \sum_{z \in \ALPHABET S} P_{s'z} v_z \Biggr). \end{align*}\] The total-variation / span bound from earlier gives, for each pair $(s,s')$, \[ \ABS{\sum_{z} P_{sz} v_z - \sum_{z} P_{s'z} v_z} \le \tfrac12 \SPAN(v)\, d_{\mathrm{TV}}(P_{s\cdot}, P_{s'\cdot}). \] Taking the maximum over pairs yields $\SPAN(Pv) \le λ(P) \SPAN(v)$.

It remains to show that the constant is sharp. If $λ(P) = 0$, then $P$ has identical rows, so $\SPAN(Pv) = 0 = λ(P) \SPAN(v)$ for all $v$. Suppose $λ(P) > 0$. Using $\sum_z \ABS{a_z-b_z} = 2\sum_z [a_z-b_z]^{+}$ for probability vectors $a,b$, we may rewrite \[ λ(P) = \max_{s,s' \in \ALPHABET S} \sum_{z \in \ALPHABET S} \bigl[ P_{sz} - P_{s'z} \bigr]^{+}. \] Let $s^*$ and $s'^*$ attain the maximum, and define $v$ by \[ v_z = \IND\{ P_{s^*z} > P_{s'^*z} \}. \] Then $\SPAN(v) = 1$ and \[\begin{align*} \SPAN(Pv) &\ge \sum_{z \in \ALPHABET S} P_{s^* z} v_z - \sum_{z \in \ALPHABET S} P_{s'^* z} v_z \\ &= \sum_{z \in \ALPHABET S} \bigl[ P_{s^*z} - P_{s'^*z} \bigr]^{+} \\ &= λ(P) \SPAN(v). \end{align*}\] Combined with the upper bound, $\SPAN(Pv) = λ(P) \SPAN(v)$.

Proposition 3.2 illustrates the “averaging” property of a transition matrix: multiplying by $P$ cannot increase the span by more than the worst total-variation gap between any two rows. When $P$ is a square matrix, $λ(P)$ is called the ergodicity coefficient. An equivalent expression, obtained from $|a-b| = (a+b)-2\min(a,b)$, is \[ λ(P) = 1 - \min_{s, s' \in \ALPHABET S} \sum_{z \in \ALPHABET S} \min\{ P_{sz}, P_{s'z} \}. \] The ergodicity coefficient is an upper bound on the second largest eigenvalue of $P$. It equals $0$ if all rows of $P$ are equal and equals $1$ if at least two rows of $P$ are orthogonal. From a different perspective, $λ(P) < 1$ if for each pair of states there exists at least one state which they both can reach with positive probability in one step.

Remark

Note that \[\begin{equation}\label{eq:ergodicity-bound} λ(P) \le 1 - \sum_{z \in \ALPHABET S} \min_{s \in \ALPHABET S} P_{sz} =: λ'(P) \end{equation}\] which is easier to compute.

3.7 Span of the value functions

For an MDP $\ALPHABET M$, define the contraction factor at time $t$ by the same idea, now maximized over controlled transitions: \[\begin{equation}\label{eq:contraction} λ_t = \frac12 \max_{\substack{ s,s' \in \ALPHABET S \\ a \in \ALPHABET A(s),\ a' \in \ALPHABET A(s')}} d_{\mathrm{TV}}\bigl( P_t(\cdot \mid s,a),\, P_t(\cdot \mid s', a') \bigr). \end{equation}\] Equivalently, \[ λ_t = \frac12 \max_{\substack{ s,s' \\ a,a'}} \sum_{z \in \ALPHABET S} \ABS{P_t(z \mid s,a) - P_t(z \mid s', a')}, \] or $λ_t = \max λ(\bar P)$ over all two-row stochastic matrices $\bar P$ formed by a pair of controlled transitions at time $t$. In particular, $λ_t \in [0, 1]$.

Lemma 3.1 For every policy $π_t$, \[ λ_t \ge λ(P^{π_t}_t). \]

Proof

Every pair of rows of $P^{π_t}_t$ is of the form $\bigl(P_t(\cdot \mid s, π_t(s)),\, P_t(\cdot \mid s', π_t(s'))\bigr)$ for some $s,s'$, hence is one of the controlled pairs appearing in $\eqref{eq:contraction}$. Therefore the maximum that defines $λ(P^{π_t}_t)$ cannot exceed $λ_t$.

For a cost function $c_t \colon \ALPHABET S \times \ALPHABET A \to \reals$, and more generally for any $q \in \ALPHABET Q$, write \[ \SPAN(q) = \sup_{(s,a) \in \ALPHABET S \times \ALPHABET A} q(s,a) - \inf_{(s,a) \in \ALPHABET S \times \ALPHABET A} q(s,a). \] In particular, $\SPAN(c_t)$ is the span of the one-step cost viewed as an element of $\ALPHABET Q$. For $v \in \ALPHABET V$ we continue to write $\SPAN(v) = \sup_s v(s) - \inf_s v(s)$.

We now track span through the factorization $\BELLMAN = \ALPHABET T \circ \ENV$: first what $\ENV_t$ does, then what the action selection operators do, and finally the composition.

Lemma 3.2 (Span through the environment operator) For any $v, v_1, v_2 \in \ALPHABET V$, \[\begin{align*} \SPAN(\ENV_t v_1 - \ENV_t v_2) &\le λ_t\, \SPAN(v_1 - v_2), \\ \SPAN(\ENV_t v) &\le \SPAN(c_t) + λ_t\, \SPAN(v). \end{align*}\]

Proof

Write $δ = v_1 - v_2$. Then \[ [\ENV_t v_1 - \ENV_t v_2](s,a) = \sum_{z \in \ALPHABET S} P_t(z \mid s,a)\, δ(z). \] Hence \[\begin{align*} \SPAN(\ENV_t v_1 - \ENV_t v_2) &= \max_{(s,a),(s',a')} \Biggl( \sum_{z} P_t(z \mid s,a)\, δ(z) - \sum_{z} P_t(z \mid s',a')\, δ(z) \Biggr). \end{align*}\] For each fixed pair of controlled transitions, the total-variation / span bound gives \[ \ABS{\sum_{z} P_t(z \mid s,a)\, δ(z) - \sum_{z} P_t(z \mid s',a')\, δ(z)} \le \tfrac12 \SPAN(δ)\, d_{\mathrm{TV}}\bigl(P_t(\cdot \mid s,a),\, P_t(\cdot \mid s',a')\bigr). \] Taking the maximum over pairs and using $\eqref{eq:contraction}$ yields the first claim.

For the second claim, write $[\DYNAMICS_t v](s,a) = \sum_z P_t(z \mid s,a)\, v(z)$, so that $\ENV_t v = c_t + \DYNAMICS_t v$. Note that $\ENV_t 0 = c_t$, hence $\ENV_t v - \ENV_t 0 = \DYNAMICS_t v$. The first claim with $(v_1,v_2)=(v,0)$ therefore yields $\SPAN(\DYNAMICS_t v) \le λ_t\, \SPAN(v)$, and subadditivity of $\SPAN$ gives \[ \SPAN(\ENV_t v) \le \SPAN(c_t) + \SPAN(\DYNAMICS_t v) \le \SPAN(c_t) + λ_t\, \SPAN(v). \]

Lemma 3.3 (Span through the action selection operators) For any $q, q_1, q_2 \in \ALPHABET Q$ and any (possibly randomized) policy $π$, \[\begin{align*} \SPAN(\ALPHABET T^π q_1 - \ALPHABET T^π q_2) &\le \SPAN(q_1 - q_2), \\ \SPAN(\ALPHABET T^\star q_1 - \ALPHABET T^\star q_2) &\le \SPAN(q_1 - q_2), \end{align*}\] and likewise \[ \SPAN(\ALPHABET T^π q) \le \SPAN(q), \qquad \SPAN(\ALPHABET T^\star q) \le \SPAN(q). \]

Proof

Write $δ = q_1 - q_2$. For the policy action selection operator, \[ [\ALPHABET T^π q_1 - \ALPHABET T^π q_2](s) = \sum_{a \in \ALPHABET A} π(a \mid s)\, δ(s,a), \] which is a convex combination of values of $δ$. Therefore every value of $\ALPHABET T^π q_1 - \ALPHABET T^π q_2$ lies between $\inf δ$ and $\sup δ$, and the span bound follows. The same argument with $q_2 = 0$ gives $\SPAN(\ALPHABET T^π q) \le \SPAN(q)$.

For the optimality action selection operator, let \[\begin{align*} s^* &= \arg\max_{s} \bigl([\ALPHABET T^\star q_1](s) - [\ALPHABET T^\star q_2](s)\bigr), \\ s_* &= \arg\min_{s} \bigl([\ALPHABET T^\star q_1](s) - [\ALPHABET T^\star q_2](s)\bigr), \end{align*}\] and let $a_2^\star \in \arg\min_a q_2(s^*,a)$ and $a_1^\star \in \arg\min_a q_1(s_*,a)$. Then \[ [\ALPHABET T^\star q_1](s^*) - [\ALPHABET T^\star q_2](s^*) \le q_1(s^*, a_2^\star) - q_2(s^*, a_2^\star) = δ(s^*, a_2^\star) \] and \[ [\ALPHABET T^\star q_1](s_*) - [\ALPHABET T^\star q_2](s_*) \ge q_1(s_*, a_1^\star) - q_2(s_*, a_1^\star) = δ(s_*, a_1^\star). \] Hence \[ \SPAN(\ALPHABET T^\star q_1 - \ALPHABET T^\star q_2) \le δ(s^*, a_2^\star) - δ(s_*, a_1^\star) \le \SPAN(δ). \] The absolute bound $\SPAN(\ALPHABET T^\star q) \le \SPAN(q)$ is the special case $q_2 = 0$, or follows because the range of $s \mapsto \min_a q(s,a)$ is contained in the range of $q$.

Composing the two lemmas recovers span contraction for the Bellman operators. For a fixed policy the model-side constant can be sharpened from $λ_t$ to $λ(P^π_t)$.

Theorem 3.1 (Span contraction of Bellman operators) For any $v_1, v_2 \in \ALPHABET V$ and any policy $π$, \[\begin{align*} \SPAN(\BELLMAN^π_t v_1 - \BELLMAN^π_t v_2) &\le λ(P^π_t)\, \SPAN(v_1 - v_2), \\ \SPAN(\BELLMAN^\star_t v_1 - \BELLMAN^\star_t v_2) &\le λ_t\, \SPAN(v_1 - v_2). \end{align*}\]

Proof

For the optimality operator, \[ \SPAN(\BELLMAN^\star_t v_1 - \BELLMAN^\star_t v_2) = \SPAN\bigl(\ALPHABET T^\star \ENV_t v_1 - \ALPHABET T^\star \ENV_t v_2\bigr) \le \SPAN(\ENV_t v_1 - \ENV_t v_2) \le λ_t\, \SPAN(v_1 - v_2), \] by Lemma 3.3 and Lemma 3.2.

For the policy operator, $\BELLMAN^π_t v_1 - \BELLMAN^π_t v_2 = P^π_t (v_1 - v_2)$, so \[ \SPAN(\BELLMAN^π_t v_1 - \BELLMAN^π_t v_2) = \SPAN\bigl(P^π_t (v_1 - v_2)\bigr) \le λ(P^π_t)\, \SPAN(v_1 - v_2) \] by Proposition 3.2. (Alternatively, $\BELLMAN^π_t = \ALPHABET T^π \circ \ENV_t$ and the same argument as above gives the weaker constant $λ_t$; the matrix form uses that only the rows selected by $π$ appear.)

Lemma 3.4 (One-step span bound) For any $v_{t+1} \colon \ALPHABET S \to \reals$ and any decision rule $π_t$, \[\begin{align*} \SPAN(\BELLMAN^{π_t}_t v_{t+1}) &\le \SPAN(c_t) + λ(P^{π_t}_t)\, \SPAN(v_{t+1}), \\ \SPAN(\BELLMAN^\star_t v_{t+1}) &\le \SPAN(c_t) + λ_t\, \SPAN(v_{t+1}). \end{align*}\]

Proof

For the optimality operator, \[ \SPAN(\BELLMAN^\star_t v_{t+1}) = \SPAN\bigl(\ALPHABET T^\star \ENV_t v_{t+1}\bigr) \le \SPAN(\ENV_t v_{t+1}) \le \SPAN(c_t) + λ_t\, \SPAN(v_{t+1}), \] by Lemma 3.3 and Lemma 3.2.

For the policy operator, write $c^{π_t}_t(s) = c_t(s, π_t(s))$. Then $\BELLMAN^{π_t}_t v_{t+1} = c^{π_t}_t + P^{π_t}_t v_{t+1}$, so \[ \SPAN(\BELLMAN^{π_t}_t v_{t+1}) \le \SPAN(c^{π_t}_t) + \SPAN(P^{π_t}_t v_{t+1}) \le \SPAN(c_t) + λ(P^{π_t}_t)\, \SPAN(v_{t+1}), \] where the last step uses Proposition 3.2 and $\SPAN(c^{π_t}_t) \le \SPAN(c_t)$.

Theorem 3.2 (Span of the value functions) Assume $V^π_{T+1} = V^\star_{T+1} = 0$. Then for every $t \in \{1,\ldots,T\}$ and every policy $π = (π_t,\ldots,π_T)$, \[\begin{align*} \SPAN(V^π_t) &\le \sum_{τ=t}^{T} \Biggl( \prod_{k=t}^{τ-1} λ(P^{π_k}_k) \Biggr) \SPAN(c_τ), \\ \SPAN(V^\star_t) &\le \sum_{τ=t}^{T} \Biggl( \prod_{k=t}^{τ-1} λ_k \Biggr) \SPAN(c_τ), \end{align*}\] where an empty product equals $1$. In particular, if $\bar λ \ge λ_t$ for all $t$, then \[ \SPAN(V^\star_t) \le \sum_{τ=t}^{T} \bar λ^{τ-t}\, \SPAN(c_τ). \] A similar bound holds for $V^π$: if $\bar λ \ge λ(P^{π_k}_k)$ for all $k$ (e.g., any $\bar λ$ that dominates all $λ_t$), then \[ \SPAN(V^π_t) \le \sum_{τ=t}^{T} \bar λ^{τ-t}\, \SPAN(c_τ). \]

Proof

At time $T+1$ the claims are immediate: $\SPAN(V^π_{T+1}) = \SPAN(V^\star_{T+1}) = 0$.

Fix $t \le T$ and assume the bound holds at time $t+1$. Since $V^π_t = \BELLMAN^{π_t}_t V^π_{t+1}$, Lemma 3.4 yields \[ \SPAN(V^π_t) \le \SPAN(c_t) + λ(P^{π_t}_t)\, \SPAN(V^π_{t+1}). \] Substituting the induction hypothesis for $\SPAN(V^π_{t+1})$ and collecting coefficients of each $\SPAN(c_τ)$ gives the claimed formula at time $t$. The same argument with $\BELLMAN^\star_t$, $λ_t$, and $V^\star_{t+1}$ proves the bound for $V^\star_t$.

As anticipated in the IPM discussion, a bound on $\SPAN(V^\star_t)$ (or $\SPAN(V^π_t)$) yields an instance-independent estimate of how much a total-variation perturbation of the model can change the corresponding value.

3.8 Lipschitz continuity

Just as a bound on $\SPAN(v)$ controls the impact of total-variation model error, a bound on $\operatorname{Lip}(v)$ controls the impact of Wasserstein model error. We first record basic properties of $\operatorname{Lip}$, then propagate Lipschitz constants through dynamic programming.

3.8.1 Lipschitz continuous functions

We state a few basic properties of $\operatorname{Lip}$.

$\operatorname{Lip}(v) \ge 0$ for all $v$.
$\operatorname{Lip}(v) = 0$ if and only if $v$ is constant.
$\operatorname{Lip}(m v) = |m|\, \operatorname{Lip}(v)$ for all $m \in \reals$.
$\operatorname{Lip}(v+w) \le \operatorname{Lip}(v) + \operatorname{Lip}(w)$.
If $\{v_i\}_{i \in I}$ is a family of functions with $\sup_i v_i(s) < ∞$ for each $s$, then \[ \operatorname{Lip}\bigl(\sup_{i \in I} v_i\bigr) \le \sup_{i \in I} \operatorname{Lip}(v_i), \] and the same holds with $\inf$ in place of $\sup$. In particular, the pointwise minimum of uniformly Lipschitz functions is Lipschitz with the same constant.

Properties 1–4 imply that $\operatorname{Lip}$ is a semi-norm on the space of Lipschitz functions.

3.9 Lipschitz constants of the value functions

Fix an MDP $\ALPHABET M$ whose state space is a metric space $(\ALPHABET S, d_{\ALPHABET S})$. We say that the model is Lipschitz at time $t$ with constants $(L^c_t, L^P_t)$ if for all $s,\tilde s \in \ALPHABET S$ and all $a \in \ALPHABET A$, \[\begin{equation}\label{eq:lipschitz-model} \ABS{c_t(s,a)-c_t(\tilde s,a)} \le L^c_t\, d_{\ALPHABET S}(s,\tilde s), \quad W_1\bigl(P_t(\cdot \mid s,a),\, P_t(\cdot \mid \tilde s,a)\bigr) \le L^P_t\, d_{\ALPHABET S}(s,\tilde s). \end{equation}\] Thus the one-step cost and the transition kernel are Lipschitz in the state, uniformly over actions.

As with span, we track Lipschitz constants through $\ENV_t$ and then through the action selection operators.

Lemma 3.5 (Lipschitz constants through the environment operator) Suppose $\eqref{eq:lipschitz-model}$ holds at time $t$, and let $v \colon \ALPHABET S \to \reals$ be Lipschitz. Then for every action $a$, the map $s \mapsto [\ENV_t v](s,a)$ is Lipschitz with \[ \operatorname{Lip}\bigl([\ENV_t v](\cdot, a)\bigr) \le L^c_t + L^P_t\, \operatorname{Lip}(v). \]

Proof

Fix $a$. For any $s,\tilde s$, \[\begin{align*} \ABS{[\ENV_t v](s,a)-[\ENV_t v](\tilde s,a)} &\le \ABS{c_t(s,a)-c_t(\tilde s,a)} + \ABS{\sum_{s' \in \ALPHABET S} P_t(s' \mid s,a)\, v(s') - \sum_{s' \in \ALPHABET S} P_t(s' \mid \tilde s,a)\, v(s')} \\ &\le L^c_t\, d_{\ALPHABET S}(s,\tilde s) + \operatorname{Lip}(v)\, W_1\bigl(P_t(\cdot \mid s,a),\, P_t(\cdot \mid \tilde s,a)\bigr) \\ &\le \bigl( L^c_t + L^P_t\, \operatorname{Lip}(v) \bigr) d_{\ALPHABET S}(s,\tilde s), \end{align*}\] where the second step uses Proposition 3.1.

Lemma 3.6 (Lipschitz constants through the action selection operators) Let $q \in \ALPHABET Q$ be such that $q(\cdot, a)$ is Lipschitz for every $a$, and write \[ L^q \coloneqq \sup_{a \in \ALPHABET A} \operatorname{Lip}\bigl(q(\cdot, a)\bigr). \] Then \[ \operatorname{Lip}(\ALPHABET T^\star q) \le L^q. \] If in addition $π$ is a constant decision rule (the same action in every state), then \[ \operatorname{Lip}(\ALPHABET T^π q) \le L^q. \]

Proof

Since $\ALPHABET T^\star q = \min_a q(\cdot, a)$, property 5 of $\operatorname{Lip}$ yields $\operatorname{Lip}(\ALPHABET T^\star q) \le \sup_a \operatorname{Lip}(q(\cdot,a)) = L^q$. If $π(s) ≡ a_0$, then $\ALPHABET T^π q = q(\cdot, a_0)$, so the same bound holds.

Lemma 3.7 (One-step Lipschitz bound) Suppose $\eqref{eq:lipschitz-model}$ holds at time $t$, and let $v_{t+1} \colon \ALPHABET S \to \reals$ be Lipschitz. Then \[ \operatorname{Lip}(\BELLMAN^\star_t v_{t+1}) \le L^c_t + L^P_t\, \operatorname{Lip}(v_{t+1}). \] If in addition $π_t$ is a constant decision rule, then the same bound holds for $\BELLMAN^{π_t}_t v_{t+1}$.

Proof

By Lemma 3.5, \[ \sup_a \operatorname{Lip}\bigl([\ENV_t v_{t+1}](\cdot, a)\bigr) \le L^c_t + L^P_t\, \operatorname{Lip}(v_{t+1}). \] Since $\BELLMAN^\star_t v_{t+1} = \ALPHABET T^\star \ENV_t v_{t+1}$, Lemma 3.6 gives the claim. The constant-action case is $\BELLMAN^{π_t}_t = \ALPHABET T^{π_t} \circ \ENV_t$.

Theorem 3.3 (Lipschitz constants of the value functions) Assume $V^\star_{T+1} = 0$ and that $\eqref{eq:lipschitz-model}$ holds at every time. Then for every $t \in \{1,\ldots,T\}$, \[ \operatorname{Lip}(V^\star_t) \le \sum_{τ=t}^{T} \Biggl( \prod_{k=t}^{τ-1} L^P_k \Biggr) L^c_τ, \] where an empty product equals $1$. In particular, if $\bar L^P \ge L^P_t$ for all $t$, then \[ \operatorname{Lip}(V^\star_t) \le \sum_{τ=t}^{T} (\bar L^P)^{τ-t}\, L^c_τ. \]

Proof

At time $T+1$ we have $\operatorname{Lip}(V^\star_{T+1}) = 0$. Fix $t \le T$ and assume the bound holds at time $t+1$. Since $V^\star_t = \BELLMAN^\star_t V^\star_{t+1}$, Lemma 3.7 yields \[ \operatorname{Lip}(V^\star_t) \le L^c_t + L^P_t\, \operatorname{Lip}(V^\star_{t+1}). \] Substituting the induction hypothesis and collecting coefficients of each $L^c_τ$ gives the claimed formula. The recursion for $L^V_t$ is exactly this one-step inequality written as an equality for an upper bound.

3.9.1 Example: Inventory management

Consider the inventory model of Example 2.1, now viewed as an MDP on $\ALPHABET S = \reals$ (with the usual metric) and $\ALPHABET A = \reals_{\ge 0}$. Let $\ell = \max\{c_h,c_s\} = \operatorname{Lip}(h)$.

Proposition 3.3 (Lipschitz constants for inventory) The transition kernel is $1$-Lipschitz in the stock level and the expected one-step cost is $\ell$-Lipschitz in the stock level. Thus we may take \[ L^P_t = 1, \quad L^c_t = \ell, \quad t = 1,\dots,T. \] Consequently, \[ L^V_{T+1} = 0, \quad L^V_t = \ell + L^V_{t+1}, \] and hence \[ L^V_t = (T-t+1)\ell. \] The same formula holds for an approximate inventory model whenever only the demand distribution is changed.

Proof

Write $S_+ = s + a - W_t$ and $\tilde S_+ = \tilde s + a - W_t$, and let $c_t(s,a) = \EXP[p a + h(S_+)]$ denote the expected one-step cost. Fix the action $a$.

Lipschitz constant of $h$. For $x,y \in \reals$, \[ \ABS{h(x)-h(y)} \le \ell \ABS{x-y}, \] with $\ell = \max\{c_h,c_s\}$. (On each half-line $h$ is linear with slope $c_h$ or $-c_s$, and the worst slope magnitude is $\ell$; the bound also holds when $x$ and $y$ lie on opposite sides of $0$.) Thus $\operatorname{Lip}(h) = \ell$.

Transition kernel. By the dual definition of $W_1$, for any $f$ with $\operatorname{Lip}(f) \le 1$, \[\begin{align*} \ABS{\EXP\bigl[f(S_+)\bigr] - \EXP\bigl[f(\tilde S_+)\bigr]} &\le \EXP\bigl[\ABS{f(S_+)-f(\tilde S_+)}\bigr] \\ &\le \EXP\ABS{S_+-\tilde S_+} \\ &= \ABS{s-\tilde s}. \end{align*}\] Taking the supremum over all such $f$ yields $W_1\bigl(P_t(\cdot \mid s,a),P_t(\cdot \mid \tilde s,a)\bigr) \le \ABS{s-\tilde s}$. For the matching lower bound, the identity map $f(x)=x$ is $1$-Lipschitz and \[ \ABS{\EXP[S_+]-\EXP[\tilde S_+]} = \ABS{s-\tilde s}, \] so $W_1\bigl(P_t(\cdot \mid s,a),P_t(\cdot \mid \tilde s,a)\bigr) = \ABS{s-\tilde s}$. Thus we may take $L^P_t = 1$.

Expected one-step cost. The term $pa$ cancels, and Proposition 3.1 together with the transition bound above gives \[\begin{align*} \ABS{c_t(s,a)-c_t(\tilde s,a)} &= \ABS{\EXP\bigl[h(S_+)-h(\tilde S_+)\bigr]} \\ &\le \operatorname{Lip}(h)\, W_1\bigl(P_t(\cdot \mid s,a),P_t(\cdot \mid \tilde s,a)\bigr) \\ &= \ell \ABS{s-\tilde s}. \end{align*}\] Thus we may take $L^c_t = \ell$.

Substituting $L^P_t=1$ and $L^c_t=\ell$ in Theorem 3.3 yields $L^V_t = \ell + L^V_{t+1}$ with $L^V_{T+1}=0$, hence $L^V_t = (T-t+1)\ell$. The same argument applies verbatim when only the law of $W_t$ is changed.

Some authors define total variation as $\tfrac12\NORM{μ-ν}_{1}$. With that convention the factor $\tfrac12$ moves from the span into the distance.↩︎

3.1 Review

3.1.1 Policy optimization

3.1.2 Policy evaluation

3.2 Operator theoretic notation

3.2.1 Bellman operators

3.2.2 Factorization via environment and action selection operators

3.3 Motivation for model approximation

3.4 Changing measures and integral probability metrics

3.4.1 A simple \(\ell_1\) bound

3.5 Wasserstein distance

3.5.1 Integral probability metrics

3.6 Span semi-norm

3.7 Span of the value functions

3.8 Lipschitz continuity

3.8.1 Lipschitz continuous functions

3.9 Lipschitz constants of the value functions

3.9.1 Example: Inventory management