Definitions

Expected Single-Stage Cost

The expected single-stage cost under policy $\mu$ in state $x$, denoted as $\bar{g}(x,\mu(x))$, is:

$$ \underbrace{\bar{g}(x,\mu(x))}_{\substack{\text{Expected} \\ \text{single-stage cost}}} = \sum_{j=0}^n \underbrace{p_{xj}(\mu(x))}_{\substack{\text{Transition} \\ \text{probability}}} \underbrace{g(x,\mu(x),j)}_{\substack{\text{Stage cost for} \\ \text{this transition}}} $$

where:

  • $p_{xj}(\mu(x))$ is the probability of transitioning from state $x$ to state $j$ under action $\mu(x)$
  • $g(x,\mu(x),j)$ is the stage cost for this transition
  • The sum is over all possible next states $j$

This represents the immediate expected cost when taking the action prescribed by policy $\mu$ in state $x$.

Cost-to-Go Function for a Given Policy

For a given stationary policy $\mu$, the cost-to-go function $J_\mu(x)$ represents the expected total cost incurred when starting from state $x$ and following policy $\mu$ until reaching the terminal state. It can be expressed recursively as:

$$ \underbrace{J_\mu(x)}_{\substack{\text{Total expected} \\ \text{cost-to-go}}} = \underbrace{\bar{g}(x,\mu(x))}_{\substack{\text{Expected} \\ \text{immediate cost}}} + \underbrace{\sum_{j=0}^n p_{xj}(\mu(x))J_\mu(j)}_{\substack{\text{Expected future cost} \\ \text{from next states}}} $$

where:

  • $\bar{g}(x,\mu(x))$ is the expected single-stage cost defined above
  • $p_{xj}(\mu(x))$ is the transition probability from state $x$ to state $j$ under action $\mu(x)$
  • The sum represents the expected future costs from the next state onwards
  • For the terminal state: $J_\mu(0) = 0$

Bellman Operator for a Given Policy

The Bellman operator $T_\mu$ for a given policy $\mu$ maps a cost function $J$ to a new cost function $T_\mu J$ according to:

$$ \underbrace{(T_\mu J)(x)}_{\substack{\text{Bellman operator} \\ \text{applied to } J}} = \underbrace{\bar{g}(x,\mu(x))}_{\substack{\text{Expected} \\ \text{immediate cost}}} + \underbrace{\sum_{j=0}^n p_{xj}(\mu(x))J(j)}_{\substack{\text{Expected future cost} \\ \text{from next states}}} $$

The key difference between $T_\mu J$ and $J$ is that $T_\mu J$ represents the updated cost estimates after one step of looking ahead, while $J$ represents the current cost estimates. Specifically:

  • $J$ is the current estimate of costs for each state
  • $T_\mu J$ computes new estimates by:
    1. Looking at immediate costs $\bar{g}(x,\mu(x))$
    2. Adding expected future costs based on current estimates $J$
    3. Following policy $\mu$’s actions

When $T_\mu J = J$, we have reached a fixed point where the cost estimates are consistent with the policy $\mu$.

Optimal Bellman Operator

The optimal Bellman operator $T$ maps a cost function $J$ to a new cost function $TJ$ by minimizing over all possible actions:

$$ \underbrace{(TJ)(x)}_{\substack{\text{Optimal Bellman} \\ \text{operator applied to } J}} = \min_{a \in \mathcal{A}(x)} \left\{ \underbrace{\bar{g}(x,a)}_{\substack{\text{Expected} \\ \text{immediate cost}}} + \underbrace{\sum_{j=0}^n p_{xj}(a)J(j)}_{\substack{\text{Expected future cost} \\ \text{from next states}}} \right\} $$

This operator represents one step of value iteration, finding the best action at each state given the current value estimates.

Transition Probability Matrix $P_\mu$

For a given policy $\mu$, the transition probability matrix $P_\mu$ is an $n \times n$ square matrix where element $(i,j)$ represents the probability of transitioning from state $i$ to state $j$ under policy $\mu$. Since state 0 is the terminal state, we only include states 1 through $n$ in the matrix:

$$ \underbrace{P_\mu}_{\substack{\text{Transition} \\ \text{probability matrix}}} = \begin{pmatrix} \underbrace{p_{11}(\mu(1))}_{\substack{\text{Probability of} \\ \text{1} \to \text{1 transition}}} & p_{12}(\mu(1)) & \cdots & p_{1n}(\mu(1)) \\ p_{21}(\mu(2)) & \underbrace{p_{22}(\mu(2))}_{\substack{\text{Probability of} \\ \text{2} \to \text{2 transition}}} & \cdots & p_{2n}(\mu(2)) \\ \vdots & \vdots & \ddots & \vdots \\ p_{n1}(\mu(n)) & p_{n2}(\mu(n)) & \cdots & \underbrace{p_{nn}(\mu(n))}_{\substack{\text{Probability of} \\ \text{n} \to \text{n transition}}} \end{pmatrix} $$

Note that for each row $i$:

$$ \sum_{j=0}^n p_{ij}(\mu(i)) \leq 1, \quad \forall i $$

This is because the sum of the probabilities of transitioning from state $i$ to all other states plus the probability of transitioning to the terminal state must equal 1.

Expected Stage Cost Vector $\bar{g}_\mu$

The expected stage cost vector $\bar{g}_\mu$ is an $n$-dimensional column vector where element $i$ represents the expected single-stage cost for non-terminal state $i$ under policy $\mu$:

$$ \bar{g}_\mu = \begin{pmatrix} \bar{g}(1,\mu(1)) \\ \bar{g}(2,\mu(2)) \\ \vdots \\ \bar{g}(n,\mu(n)) \end{pmatrix} $$

Matrix Notation for Bellman Operators

Using these matrix notations, we can express the Bellman operator for policy $\mu$ as:

$$ \underbrace{T_\mu J}_{\substack{\text{Bellman operator} \\ \text{for policy } \mu}} = \underbrace{\bar{g}_\mu}_{\substack{\text{Expected} \\ \text{stage cost}}} + \underbrace{P_\mu J}_{\substack{\text{Expected future} \\ \text{costs under } \mu}} $$

And for $k \geq 0$, the $k$-fold composition of the Bellman operator $T$ is:

$$ \underbrace{T^k}_{\substack{\text{k-fold} \\ \text{composition}}} = \underbrace{T(T^{k-1}J)}_{\substack{\text{Apply T operator} \\ \text{k times}}}, \quad \text{where } \underbrace{T^0 = I}_{\substack{\text{Base case:} \\ \text{Identity operator}}} $$

This matrix notation provides a compact representation of the SSP problem and facilitates the analysis of solution algorithms.

Interpretation of $T^k$ Operator

For $k=2$, the two-stage Bellman operator $T^2J(i)$ can be written as:

$$ \underbrace{T^2J(i)}_{\substack{\text{Two-stage} \\ \text{Bellman operator}}} = \underbrace{T(TJ)(i)}_{\substack{\text{Composition of} \\ \text{T operators}}} = \min_{u \in \mathcal{A}(i)} \left(\underbrace{\bar{g}(i,u)}_{\substack{\text{Immediate} \\ \text{stage cost}}} + \underbrace{\sum_{j=1}^n p_{ij}(u)TJ(j)}_{\substack{\text{Expected cost-to-go} \\ \text{after first stage}}}\right) $$

This expands to:

$$ \underbrace{T^2J(i)}_{\substack{\text{Two-stage} \\ \text{optimal cost}}} = \min_{u_1 \in \mathcal{A}(i)} \left(\underbrace{\bar{g}(i,u_1)}_{\substack{\text{First stage} \\ \text{cost}}} + \sum_{j=1}^n p_{ij}(u_1) \min_{u_2 \in \mathcal{A}(j)} \left(\underbrace{\bar{g}(j,u_2)}_{\substack{\text{Second stage} \\ \text{cost}}} + \underbrace{\sum_{k=1}^n p_{jk}(u_2)J(k)}_{\substack{\text{Expected terminal} \\ \text{cost}}}\right)\right) $$

Interpretation:

  • $T^2J(i)$ represents the optimal cost for a 2-stage problem starting in state $i$
  • It considers both:
    1. The immediate stage cost $\bar{g}(i,\cdot)$
    2. The terminal cost $J(\cdot)$

More generally, $T^kJ(i)$ represents the optimal cost of a $k$-stage problem with:

  • Initial state $i$
  • Stage cost function $\bar{g}(i,\cdot)$
  • Terminal cost function $J(\cdot)$

Mathematically:

$$ \underbrace{T^kJ(i)}_{\substack{\text{k-stage} \\ \text{optimal cost}}} = \min_{u \in \mathcal{A}(i)} \left(\underbrace{\bar{g}(i,u)}_{\substack{\text{Immediate} \\ \text{stage cost}}} + \underbrace{\sum_{j \in \mathcal{X}} p_{ij}(u)T^{k-1}J(j)}_{\substack{\text{Expected cost-to-go} \\ \text{for remaining k-1 stages}}}\right), \quad \forall i=1,\ldots,n $$

Lemmas

Lemma 1

For any two value functions $J,\bar{J} \in \mathbb{R}^n$ where $J$ is dominated by $\bar{J}$, i.e.,

$$ \underbrace{J(i)}_{\substack{\text{Cost-to-go} \\ \text{for state } i}} \leq \underbrace{\bar{J}(i)}_{\substack{\text{Upper bound on} \\ \text{cost-to-go}}} \quad \forall i \in \{1,\ldots,n\} $$

The following monotonicity properties hold for any stationary policy $\mu$:

  1. For the optimal Bellman operator $T$:

    $$ \underbrace{T^kJ(i)}_{\substack{\text{k-stage optimal cost} \\ \text{with initial value } J}} \leq \underbrace{T^k\bar{J}(i)}_{\substack{\text{k-stage optimal cost} \\ \text{with initial value } \bar{J}}} \quad \forall k \geq 0, \forall i=1,\ldots,n $$

  2. For the policy-specific Bellman operator $T_\mu$:

    $$ \underbrace{T_\mu^kJ(i)}_{\substack{\text{k-stage cost} \\ \text{under policy } \mu}} \leq \underbrace{T_\mu^k\bar{J}(i)}_{\substack{\text{k-stage cost with} \\ \text{upper bound initial value}}} \quad \forall k \geq 0, \forall i=1,\ldots,n $$

Intuition: This lemma establishes the monotonicity property of Bellman operators. If we start with two cost-to-go functions where one dominates the other ($J \leq \bar{J}$), applying the Bellman operator $k$ times preserves this ordering.

This property is crucial for proving convergence of value iteration and policy iteration algorithms.

Lemma 2

For any $k \geq 0$, vector $J \in \mathbb{R}^n$, stationary policy $\mu$, and unit vector $e=(1,1,\ldots,1)^T \in \mathbb{R}^n$, the following inequalities hold:

  1. For the optimal Bellman operator $T$:

    $$ \underbrace{(T^k(J+ve))(i)}_{\substack{\text{k-stage optimal cost} \\ \text{with shifted initial value}}} \leq \underbrace{(T^kJ)(i)}_{\substack{\text{k-stage} \\ \text{optimal cost}}} + v \quad \forall i=1,\ldots,n $$

  2. For the policy-specific operator $T_\mu$:

    $$ \underbrace{(T_\mu^k(J+ve))(i)}_{\substack{\text{k-stage cost under policy } \mu \\ \text{with shifted initial value}}} \leq \underbrace{(T_\mu^kJ)(i)}_{\substack{\text{k-stage cost} \\ \text{under policy } \mu}} + v \quad \forall i=1,\ldots,n $$

where $v \geq 0$ is a scalar. The inequality is reversed if $v < 0$.

Intuition: This lemma describes how the Bellman operators behave when we add a constant value $v$ to all states. It shows that:

  • If we add a positive constant $v$ to all terminal costs (J+ve)
  • The resulting k-stage optimal costs will increase by at most $v$
  • This holds for both the optimal operator $T$ and policy-specific operator $T_\mu$

This property helps establish bounds on how value functions change when costs are perturbed uniformly across states.

Assumptions

Assumption 1: Existence of Proper Policy

There exists at least one proper policy. A proper policy is one that reaches the terminal state with probability 1 from any initial state.

Mathematical Formulation: $\exists \mu$ such that starting from any non-terminal state $i$, following $\mu$ leads to the terminal state with probability 1.

Importance:

  • Ensures the problem is well-defined
  • Guarantees existence of finite optimal costs
  • Without this, some policies might never reach the goal

Assumption 2: Infinite Cost for Improper Policies

For any improper policy $\mu$ and any state $i$ from which the terminal state is not reached with probability 1, the cost-to-go is infinite:

$$ \underbrace{J_\mu(i)}_{\substack{\text{Cost-to-go} \\ \text{under policy } \mu}} = \infty \quad \text{if } \underbrace{\mu \text{ is improper}}_{\substack{\text{Does not reach} \\ \text{terminal state}}} \text{ at state } i $$

Importance:

  • Penalizes policies that might get stuck in cycles
  • Ensures optimal policy will be proper
  • Forces convergence to terminal state

These assumptions together ensure:

  1. Problem has a meaningful solution (Assumption 1)
  2. Solution will reach the goal state (Assumption 2)
  3. Optimal costs are well-defined and finite

Propositions

Proposition 1(a)

For any proper policy $\mu$, the associated cost vector $J_\mu$ satisfies the following key properties:

  1. Convergence Property: For any initial cost vector $J \in \mathbb{R}^n$:

    $$ \underbrace{J_\mu}_{\substack{\text{Cost vector} \\ \text{under policy } \mu}} = \lim_{k \to \infty} \underbrace{T_\mu^k J}_{\substack{\text{k iterations of} \\ \text{Bellman operator}}} $$

  2. Uniqueness Property: $J_\mu$ is the unique fixed point solution to the Bellman equation:

    $$ \underbrace{J_\mu}_{\substack{\text{Cost vector} \\ \text{under policy } \mu}} = \underbrace{T_\mu J_\mu}_{\substack{\text{Bellman operator} \\ \text{applied to } J_\mu}} $$

Intuition: This proposition establishes two key properties of the cost vector $J_\mu$ for proper policies:

  1. It can be obtained through repeated application of the Bellman operator $T_\mu$
  2. It uniquely satisfies the Bellman equation for policy $\mu$

These properties are fundamental for:

  • Proving convergence of policy evaluation
  • Establishing uniqueness of cost-to-go values
  • Justifying iterative methods for computing $J_\mu$

The uniqueness property is particularly important as it ensures that policy evaluation has a well-defined solution.

Proposition 1(b)

For a stationary policy $\mu$, if there exists a vector $J$ satisfying $J \geq T_\mu J$, then $\mu$ is proper.

$$ \underbrace{J \geq T_\mu J}_{\substack{\text{Vector inequality} \\ \text{component-wise}}} \implies \underbrace{\mu \text{ is proper}}_{\substack{\text{Reaches terminal} \\ \text{state w.p. 1}}} $$

Key ideas:

  • The inequality $J \geq T_\mu J$ indicates that applying the Bellman operator results in a decrease (or no increase) in the cost estimates.
  • An improper policy, on the other hand, would lead to non-decreasing or even infinite costs, thereby violating this inequality.

Proposition 2(a)

The optimal cost vector $J^*$ satisfies the following key properties:

  1. Bellman Equation: $J^*$ is a solution to the Bellman equation:

    $$ \underbrace{J^*}_{\substack{\text{Optimal} \\ \text{cost vector}}} = \underbrace{TJ^*}_{\substack{\text{Optimal Bellman} \\ \text{operator applied}}} $$

  2. Uniqueness: Moreover, $J^*$ is the unique solution to the Bellman equation.

Intuition: This proposition establishes that:

  • The optimal cost vector $J^*$ satisfies the Bellman optimality equation
  • There is only one such solution, making $J^*$ well-defined
  • This uniqueness is crucial for:
    • Guaranteeing convergence of value iteration
    • Ensuring the optimal policy is well-defined
    • Justifying dynamic programming approaches

The uniqueness property is particularly important as it ensures that finding the optimal solution is a well-posed problem with a single, definitive answer.

Proposition 2(b)

For any initial cost vector $J$, repeated application of the optimal Bellman operator $T$ converges to the optimal cost vector $J^*$:

$$ \underbrace{\lim_{k \to \infty} T^k(J)}_{\substack{\text{Limit of repeated} \\ \text{Bellman operations}}} = \underbrace{J^*}_{\substack{\text{Optimal} \\ \text{cost vector}}} \quad \forall J \in \mathbb{R}^n $$

Key implications: This proposition is crucial because it:

  • Value iteration algorithm converges regardless of initialization to the unique optimal cost vector $J^*$
  • Shows robustness to initial conditions since it holds for any starting cost estimates $J$
  • Guarantees convergence and justifies practical implementations of value iteration algorithms

The convergence property ensures that we can find the optimal solution through iterative application of the Bellman operator, regardless of our starting point.

Proposition 2(c)

For a stationary policy $\mu$, optimality is achieved if and only if the policy satisfies:

$$ \underbrace{T_\mu J^*}_{\substack{\text{Policy Bellman} \\ \text{operator applied}}} = \underbrace{TJ^*}_{\substack{\text{Optimal Bellman} \\ \text{operator applied}}} $$

Key implications: This proposition establishes that:

  • A policy is optimal if and only if its Bellman operator $T_\mu$ produces the same result as the optimal Bellman operator $T$ when applied to $J^*$, meaning it must choose actions that achieve the minimum in the optimal Bellman equation at every state
  • The condition $T_\mu J^* = TJ^*$ effectively means the policy $\mu$ selects actions that minimize the sum of immediate cost and expected future cost at each state, with no other policy able to achieve lower costs when starting from any state
  • This provides a practical way to verify optimality of a policy by checking if it satisfies this equality, as the policy makes optimal decisions based on the true optimal cost-to-go values $J^*$

Proposition 3(Contraction property)

For any $\beta \in (0,1)$, the optimal Bellman operator $T$ and policy Bellman operator $T_\mu$ are contraction mappings with respect to the weighted maximum norm $|\cdot|_\beta$:

$$ \underbrace{\|TJ - T\bar{J}\|_\beta}_{\substack{\text{Distance between} \\ \text{operator outputs}}} \leq \underbrace{\beta\|J - \bar{J}\|_\beta}_{\substack{\text{Scaled distance} \\ \text{between inputs}}} \quad \forall J,\bar{J} \in \mathbb{R}^n $$ $$ \underbrace{\|T_\mu J - T_\mu\bar{J}\|_\beta}_{\substack{\text{Distance between} \\ \text{operator outputs}}} \leq \underbrace{\beta\|J - \bar{J}\|_\beta}_{\substack{\text{Scaled distance} \\ \text{between inputs}}} \quad \forall J,\bar{J} \in \mathbb{R}^n $$

Key implications: This proposition establishes that both Bellman operators are contraction mappings with contraction factor $\beta$, which:

  • Brings vectors closer together when applied, with the distance between outputs being at most $\beta$ times the distance between inputs
  • Ensures geometric convergence to unique fixed points at a rate determined by $\beta$ (via Banach fixed-point theorem)
  • Provides crucial theoretical foundations for:
    • Proving value iteration convergence regardless of starting point
    • Guaranteeing uniqueness of optimal solutions
    • Establishing error bounds for approximate methods
    • Justifying practical implementations of dynamic programming algorithms

This mathematical foundation justifies why dynamic programming algorithms like value iteration and policy iteration are guaranteed to work.

Summary

Definitions

  • Expected single-stage cost: $\bar{g}(x,\mu(x)) = \sum_{j=0}^n \underbrace{p_{xj}(\mu(x))}_{\substack{\text{Transition} \\ \text{probability}}} \underbrace{g(x,\mu(x),j)}_{\substack{\text{Stage cost for} \\ \text{this transition}}}$
  • Cost-to-go function: $J_\mu(x) = \underbrace{\bar{g}(x,\mu(x))}_{\substack{\text{Expected} \\ \text{immediate cost}}} + \underbrace{\sum_{j=0}^n p_{xj}(\mu(x))J_\mu(j)}_{\substack{\text{Expected future cost} \\ \text{from next states}}}$
  • Bellman operator: $(T_\mu J)(x) = \underbrace{\bar{g}(x,\mu(x))}_{\substack{\text{Expected} \\ \text{immediate cost}}} + \underbrace{\sum_{j=0}^n p_{xj}(\mu(x))J(j)}_{\substack{\text{Expected future cost} \\ \text{from next states}}}$
  • Optimal Bellman operator: $(TJ)(x) = \min_{a \in \mathcal{A}(x)} \left(\underbrace{\bar{g}(x,a)}_{\substack{\text{Expected} \\ \text{immediate cost}}} + \underbrace{\sum_{j=0}^n p_{xj}(a)J(j)}_{\substack{\text{Expected future cost} \\ \text{from next states}}}\right)$
  • Transition probability matrix: $P_\mu = [p_{ij}(\mu(i))]_{i,j=1}^n$
  • Matrix notation for Bellman operators: $\underbrace{T_\mu J}_{\substack{\text{Bellman operator} \\ \text{for policy } \mu}} = \underbrace{\bar{g}_\mu}_{\substack{\text{Expected} \\ \text{stage cost}}} + \underbrace{P_\mu J}_{\substack{\text{Expected future} \\ \text{costs under } \mu}}$
  • Interpretation of $T^k$ operator: $\underbrace{T^kJ(i)}_{\substack{\text{k-stage optimal cost}}} = \min_{u \in \mathcal{A}(i)} \left(\underbrace{\bar{g}(i,u)}_{\substack{\text{Immediate} \\ \text{stage cost}}} + \underbrace{\sum_{j \in \mathcal{X}} p_{ij}(u)T^{k-1}J(j)}_{\substack{\text{Expected cost-to-go} \\ \text{for remaining k-1 stages}}}\right), \quad \forall i=1,\ldots,n$

Lemmas

  • Lemma 1(monotonicity): If $J \leq \bar{J}$, then $\underbrace{T^kJ(i)}_{\substack{\text{k-stage optimal cost} \\ \text{with initial value } J}} \leq \underbrace{T^k\bar{J}(i)}_{\substack{\text{k-stage optimal cost} \\ \text{with initial value } \bar{J}}} \quad$ & $\underbrace{T_\mu^kJ(i)}_{\substack{\text{k-stage cost} \\ \text{under policy } \mu}} \leq \underbrace{T_\mu^k\bar{J}(i)}_{\substack{\text{k-stage cost with} \\ \text{upper bound initial value}}}$
  • Lemma 2(constant shift property): $\underbrace{(T^k(J+ve))(i)}_{\substack{\text{k-stage optimal cost} \\ \text{with shifted initial value}}} \leq \underbrace{(T^kJ)(i)}_{\substack{\text{k-stage} \\ \text{optimal cost}}} + v \quad$ & $\underbrace{(T_\mu^k(J+ve))(i)}_{\substack{\text{k-stage cost under policy } \mu \\ \text{with shifted initial value}}} \leq \underbrace{(T_\mu^kJ)(i)}_{\substack{\text{k-stage cost} \\ \text{under policy } \mu}} + v \quad$ where $v \geq 0$ and the inequality is reversed if $v < 0$

Assumptions

  • Assumption 1(existence of proper policy): $\exists \mu$ such that starting from any non-terminal state $i$, following $\mu$ leads to the terminal state with probability 1.
  • Assumption 2(infinite cost for improper policies): For any improper policy $\mu$ and any state $i$ from which the terminal state is not reached with probability 1, the cost-to-go is infinite: $J_\mu(i) = \infty$ if $\mu$ is improper at state $i$

Propositions

  • Proposition 1(a)(1)(convergence property): $\underbrace{J_\mu}_{\substack{\text{Cost vector} \\ \text{under policy } \mu}} = \lim_{k \to \infty} \underbrace{T_\mu^k J}_{\substack{\text{k iterations of} \\ \text{Bellman operator}}}$
  • Proposition 1(a)(2)(uniqueness property): $J_\mu$ is the unique fixed point solution to the Bellman equation: $\underbrace{J_\mu}_{\substack{\text{Cost vector} \\ \text{under policy } \mu}} = \underbrace{T_\mu J_\mu}_{\substack{\text{Bellman operator} \\ \text{applied to } J_\mu}}$
  • Proposition 1(b): If there exists a vector $J$ satisfying $J \geq T_\mu J$, then $\mu$ is proper. $\underbrace{J \geq T_\mu J}_{\substack{\text{Vector inequality} \\ \text{component-wise}}} \implies \underbrace{\mu \text{ is proper}}_{\substack{\text{Reaches terminal} \\ \text{state w.p. 1}}}$
  • Proposition 2(a)(Bellman equation): $J^*$ is a unique solution to the Bellman equation: $\underbrace{J^*}_{\substack{\text{Optimal} \\ \text{cost vector}}} = \underbrace{TJ^*}_{\substack{\text{Optimal Bellman} \\ \text{operator applied}}}$
  • Proposition 2(b)(convergence property): For any initial cost vector $J$, repeated application of the optimal Bellman operator $T$ converges to the optimal cost vector $J^*$: $\underbrace{\lim_{k \to \infty} T^k(J)}_{\substack{\text{Limit of repeated} \\ \text{Bellman operations}}} = \underbrace{J^*}_{\substack{\text{Optimal} \\ \text{cost vector}}}$
  • Proposition 2(c)(optimality condition): For a stationary policy $\mu$, optimality is achieved if and only if the policy satisfies: $\underbrace{T_\mu J^*}_{\substack{\text{Policy Bellman} \\ \text{operator applied}}} = \underbrace{TJ^*}_{\substack{\text{Optimal Bellman} \\ \text{operator applied}}}$
  • Proposition 3(contraction property): For any $\beta \in (0,1)$, both the optimal Bellman operator $T$ and policy Bellman operator $T_\mu$ are contraction mappings with respect to the weighted maximum norm $\|\cdot\|_\beta$: - For optimal Bellman operator: $\underbrace{\|TJ - T\bar{J}\|_\beta}_{\substack{\text{Distance between} \\ \text{operator outputs}}} \leq \underbrace{\beta\|J - \bar{J}\|_\beta}_{\substack{\text{Scaled distance} \\ \text{between inputs}}} \quad \forall J,\bar{J} \in \mathbb{R}^n$ - For policy Bellman operator: $\underbrace{\|T_\mu J - T_\mu\bar{J}\|_\beta}_{\substack{\text{Distance between} \\ \text{operator outputs}}} \leq \underbrace{\beta\|J - \bar{J}\|_\beta}_{\substack{\text{Scaled distance} \\ \text{between inputs}}} \quad \forall J,\bar{J} \in \mathbb{R}^n$