In infinite horizon discounted cost problems, we consider scenarios without a termination state and an infinite sequence of decisions. Let’s understand the key components and mathematical formulation.

Problem Setting

  • State Space: Set of states $S = {1,2,…,n}$. Note that there is no terminal state unlike in finite horizon problems.
  • Action Space: For each state $i$, set of feasible actions $A(i)$
    • Total action space: $A = \bigcup_{i \in S} A(i)$
  • Cardinality: Both $|S|$ and $|A|$ are finite

Optimal Cost Function

The optimal cost function $J^*(i)$ represents the minimum total discounted cost starting from state $i$:

$$ \underbrace{J^*(i)}_{\substack{\text{Optimal cost} \\ \text{from state } i}} = \min_{u} \left[ \sum_{k=0}^{\infty} \alpha^k g(i_k,\mu(i_k),i_{k+1}) \mid i_0 = i \right] $$

where:

  • $\alpha \in (0,1)$ is the discount factor
  • $g(i,u,j)$ is the single stage transitioncost for transition from state $i$ to $j$ prescribed by policy $\mu$ at stage $k$
  • $i_k$ represents the state at stage $k$
  • $\mu(i_k)$ is the policy decision at stage $k$

Bellman Operators

There are two key Bellman operators in infinite horizon problems:

  1. Optimal Bellman Operator $T$ (maps any value function $J$ to another value function):
$$ \underbrace{(TJ)(i)}_{\substack{\text{New value function} \\ \text{at state } i}} = \underbrace{\min_{u \in A(i)}}_{\substack{\text{Minimization} \\ \text{over actions}}} \underbrace{\sum_{j \in S} p_{ij}(u)(g(i,u,j) + \alpha J(j))}_{\substack{\text{Expected cost: immediate cost} \\ \text{plus discounted future cost}}}, \quad i \in S $$
2. **Policy Bellman Operator** $T_{\mu}$ (specific to policy $\mu$):
$$ \underbrace{(T_{\mu}J)(i)}_{\substack{\text{New value function} \\ \text{at state } i}} = \underbrace{\sum_{j \in S} p_{ij}(\mu(i))(g(i,\mu(i),j) + \alpha J(j))}_{\substack{\text{Expected cost under policy } \mu: \\ \text{immediate cost plus discounted future cost}}}, \quad i \in S $$

where:

  • $p_{ij}(u)$ is the transition probability from state $i$ to $j$ under action $u$
  • $J$ is any value function
  • $\alpha$ is the discount factor that weighs future costs less than immediate costs
  • $\mu$ is a specific policy mapping states to actions

Matrix Notation

The policy Bellman operator can be expressed in matrix form for computational convenience:

Let’s break down the components:

  1. Transition Probability Matrix $P_{\mu}$:
$$ P_{\mu} = \begin{bmatrix} p_{11}(\mu(1)) & p_{12}(\mu(1)) & \cdots & p_{1n}(\mu(1)) \\ p_{21}(\mu(2)) & p_{22}(\mu(2)) & \cdots & p_{2n}(\mu(2)) \\ \vdots & \vdots & \ddots & \vdots \\ p_{n1}(\mu(n)) & p_{n2}(\mu(n)) & \cdots & p_{nn}(\mu(n)) \end{bmatrix} $$

where:

  • Each row sums to 1: $\sum_{j \in S} p_{ij}(\mu(i)) = 1$ for all $i \in S$
  • No terminal states in infinite horizon problems
  1. Stage Cost Vector $g_{\mu}$:
$$ g_{\mu} = \begin{bmatrix} \sum_{j \in S} p_{1j}(\mu(1))g(1,\mu(1),j) \\ \sum_{j \in S} p_{2j}(\mu(2))g(2,\mu(2),j) \\ \vdots \\ \sum_{j \in S} p_{nj}(\mu(n))g(n,\mu(n),j) \end{bmatrix} $$

Bellman Equation Under Policy $\mu$

The Bellman equation for a given policy $\mu$ can be written in matrix form:

$$ T_{\mu}J = g_{\mu} + \alpha P_{\mu}J $$

This compact notation helps in:

  • Understanding the structure of the problem
  • Implementing efficient computational methods
  • Analyzing convergence properties of solution algorithms

Monotonicity Lemma

For any vectors $J, \bar{J} \in \mathbb{R}^n$ such that $J(i) \leq \bar{J}(i)$ for all $i \in S$ and for any stationary policy $\mu$, the following monotonicity properties hold:

  1. For the optimal Bellman operator $T$:

    $$ (T^kJ)(i) \leq (T^k\bar{J})(i) \quad \forall i \in S, k=1,2,\ldots $$

  2. For the policy Bellman operator $T_\mu$: $$ (T_\mu^kJ)(i) \leq (T_\mu^k\bar{J})(i) \quad \forall i \in S, k=1,2,\ldots $$

This lemma establishes that:

  • Both Bellman operators preserve ordering between value functions
  • If we start with a lower value function, applying the operators repeatedly will still result in lower values
  • The monotonicity property is crucial for proving convergence of value iteration and policy iteration algorithms

Linearity Lemma

For any vectors $J, r \in \mathbb{R}^n$, scalar $\alpha$, and stationary policy $\mu$, where $e$ is a vector of all ones ($e = [1,1,\ldots,1]^T \in \mathbb{R}^n$), the following linearity properties hold:

  1. For the optimal Bellman operator $T$:

    $$ (T^k(J+re))(i) = (T^kJ)(i) + \alpha^k r \quad \forall i \in {1,2,\ldots,n}, k \geq 1 $$

  2. For the policy Bellman operator $T_\mu$: $$ (T_\mu^k(J+re))(i) = (T_\mu^kJ)(i) + \alpha^k r \quad \forall i \in {1,2,\ldots,n}, k \geq 1 $$

This lemma establishes that:

  • The Bellman operators exhibit linear behavior with respect to constant shifts
  • Adding a constant to the value function results in a scaled addition to the operated value
  • The scaling factor $\alpha^k$ reflects the discount factor raised to the power of iterations
  • This property is useful in analyzing convergence and error bounds of dynamic programming algorithms

The linearity property complements the monotonicity lemma and helps in:

  • Understanding how value functions change under constant shifts
  • Analyzing the behavior of value iteration and policy iteration
  • Deriving error bounds and convergence rates
  • Simplifying theoretical analysis of dynamic programming algorithms

Converting Discounted Cost Problems(DCP) to Stochastic Shortest Path Problems(SSPP) by adding a terminal state

Let’s understand how we can convert a discounted cost problem (DCP) into a stochastic shortest path problem (SSPP) by adding a terminal state.

Key Idea

The main concept is to introduce an artificial terminal state that captures the discounting effect through transition probabilities.

Mathematical Formulation

For a DCP with discount factor $\alpha$, we can construct an equivalent SSPP where:

  1. Terminal State Properties:

    • Add a terminal state $t$ to the state space
    • Set $g(i,u,t) = 0$ for all states $i$ and controls $u$
    • Make state $t$ cost-free and absorbing: $g(t,u,t) = 0$

  2. Transition Probabilities: For any state $i$ and control $u$:

$$ \underbrace{P(\text{termination in }k\text{th stage})}_{\text{Probability of reaching terminal state}} = \begin{cases} 1-\alpha & \text{for }k=1 \\ \alpha(1-\alpha) & \text{for }k=2 \\ \alpha^{k-1}(1-\alpha) & \text{for }k\text{th stage} \end{cases} $$

  1. Non-termination Probability: The probability of not terminating by stage $k$ is:

    $$ \begin{align*} P(\text{non-termination by stage }k) &= 1-{(1-\alpha) + \alpha(1-\alpha) + … + \alpha^{k-1}(1-\alpha)} \ &= 1-\frac{(1-\alpha)(1-\alpha^k)}{1-\alpha} = \alpha^k \end{align*} $$

  2. Expected Stage Cost: For the $k$th stage:

    $$ \underbrace{\text{Expected single stage cost}}_{\text{In }k\text{th stage}} = \alpha^k \sum_{j=1}^n p_{ij}(u)g(i,u,j) $$ where $g(i,u,t) = 0$ for the terminal state $t$

Proposition (DP Convergence)

For a discounted cost problem (DCP) with:

  • Bounded stage costs $g(i,u,j) \leq M$ for all $i,j \in S$ and $u \in A(i)$
  • Discount factor $\alpha < 1$

The optimal cost function $J^*$ satisfies:

$$ \underbrace{J^*(i)}_{\substack{\text{Optimal cost} \\ \text{starting from state }i}} = \lim_{N \to \infty} (T^NJ)(i) \quad \forall i \in S $$

where:

  • $T$ is the Bellman operator
  • $T^N$ denotes N successive applications of $T$
  • $J$ is any bounded function

In simple words, I can start with any bounded function $J$ and apply the Bellman operator $T$ $N$ times, then take the limit as $N$ approaches infinity. The limit will be the optimal cost function $J^*$.

Corollary (Policy Convergence)

For any stationary policy $\mu$, the associated cost function satisfies:

$$ \underbrace{J_{\mu}(i)}_{\substack{\text{Cost function} \\ \text{for policy }\mu}} = \lim_{N \to \infty} (T_{\mu}^NJ)(i) \quad \forall i \in S $$

where:

  • $T_{\mu}$ is the policy Bellman operator
  • $T_{\mu}^N$ denotes N successive applications of $T_{\mu}$
  • $J$ is any bounded function

In simple words, I can start with any bounded function $J$ and apply the policy Bellman operator $T_{\mu}$ $N$ times, then take the limit as $N$ approaches infinity. The limit will be the cost function $J_{\mu}$.

Corollary (Bellman Equation for Policy)

For any stationary policy $\mu$, the associated cost-to-go function $J_{\mu}$ satisfies:

$$ \underbrace{J_{\mu}(i)}_{\substack{\text{Cost-to-go} \\ \text{for state }i}} = \underbrace{\sum_{j \in S} p_{ij}(\mu(i))(g(i,\mu(i),j) + \alpha J_{\mu}(j))}_{\substack{\text{Expected cost: immediate cost} \\ \text{plus discounted future cost}}} \quad \forall i \in S $$

Moreover, $J_{\mu}$ is the unique solution to this equation within the class of bounded functions.

Necessary and Sufficient Condition for Optimality

Proposition: A stationary policy $\mu$ is optimal if and only if it attains the minimum in the Bellman equation for all states $i \in S$, i.e.:

$$ \underbrace{T_{\mu}J^* = TJ^*}_{\substack{\text{Policy } \mu \text{ achieves minimum} \ \text{in Bellman equation}}} $$

This means:

$$ \underbrace{\sum_{j \in S} p_{ij}(\mu(i))(g(i,\mu(i),j) + \alpha J^*(j))}_{\substack{\text{Cost under policy } \mu}} = \underbrace{\min_{u \in A(i)} \sum_{j \in S} p_{ij}(u)(g(i,u,j) + \alpha J^*(j))}_{\substack{\text{Minimum cost over} \\ \text{all possible actions}}} \quad \forall i \in S $$

This condition establishes that:

  • A policy is optimal if and only if it selects actions that achieve the minimum in the Bellman equation
  • The policy Bellman operator $T_{\mu}$ coincides with the optimal Bellman operator $T$ when applied to $J^*$
  • No other policy can achieve a lower cost than an optimal policy satisfying this condition

Max Norm and Contraction Properties

Let’s define the max norm $|\cdot|_{\infty}$ on $\mathbb{R}^n$ as:

$$ \underbrace{\|J\|_{\infty}}_{\substack{\text{Max norm} \\ \text{of function }J}} = \underbrace{\max_{i \in S} |J(i)|}_{\substack{\text{Maximum absolute value} \\ \text{across all states}}} $$

Proposition: For any two bounded functions $J: S \to \mathbb{R}$ and $\bar{J}: S \to \mathbb{R}$ and for all $k = 0,1,2,…$:

(a)

$$ \underbrace{\|T^kJ - T^k\bar{J}\|_{\infty}}_{\substack{\text{Distance between k-step} \\ \text{value function updates}}} \leq \underbrace{\alpha^k\|J-\bar{J}\|_{\infty}}_{\substack{\text{Discounted initial} \\ \text{distance}}} $$

(b)

$$ \underbrace{\|T*{\mu}^kJ - T*{\mu}^k\bar{J}\|_{\infty}}_{\substack{\text{Distance between k-step} \\ \text{policy updates}}} \leq \underbrace{\alpha^k\|J-\bar{J}\|_{\infty}}_{\substack{\text{Discounted initial} \\ \text{distance}}} $$

These inequalities establish that:

  • Both Bellman operators are contraction mappings with factor $\alpha$
  • The distance between value function iterates decreases exponentially
  • The convergence rate is governed by the discount factor $\alpha$
  • The results hold for both optimal and policy-specific operators

Corollary on Rate of Convergence of Value Iteration

For any bounded function $J: S \to \mathbb{R}$, we have the following convergence properties:

  1. For the optimal Bellman operator:
$$ \underbrace{\max_{i \in S} |(T^kJ)(i) - J^*(i)|}_{\substack{\text{Maximum distance from} \\ \text{optimal value function}}} \leq \underbrace{\alpha^k\max_{i \in S} |J(i)-J^*(i)|}_{\substack{\text{Discounted initial} \\ \text{distance from optimum}}} $$
  1. For the policy Bellman operator:
$$ \underbrace{\max_{i \in S} |(T_{\mu}^kJ)(i) - J_{\mu}(i)|}_{\substack{\text{Maximum distance from} \\ \text{policy value function}}} \leq \underbrace{\alpha^k\max_{i \in S} |J(i)-J_{\mu}(i)|}_{\substack{\text{Discounted initial} \\ \text{distance from policy value}}} \quad \forall k = 0,1,2,... $$
These inequalities demonstrate that:
  • The convergence to both optimal and policy-specific value functions is geometric
  • The rate of convergence is determined by the discount factor $\alpha$
  • The initial distance from the target value function affects the absolute error bound
  • The convergence is uniform across all states

Error Bounds for Value Iteration

For any bounded function $J: S \to \mathbb{R}$ and state $i \in S$, at iteration $k \geq 0$:

$$ \underbrace{(T^kJ)(i) + \underline{c}_k}_{\substack{\text{k-step value function} \\ \text{plus lower bound}}} \leq \underbrace{(T^{k+1}J)(i) + \underline{c}_{k+1}}_{\substack{\text{(k+1)-step value function} \\ \text{plus updated bound}}} \leq \underbrace{J^*(i)}_{\substack{\text{Optimal} \\ \text{value function}}} \leq \underbrace{(T^{k+1}J)(i) + \bar{c}_{k+1}}_{\substack{\text{k-step value function} \\ \text{plus upper bound}}} \leq \underbrace{(T^{k}J)(i) + \bar{c}_k}_{\substack{\text{k-step value function} \\ \text{plus upper bound}}} $$

where:

  • Lower bound sequence:
$$ \underbrace{\underline{c}_k}_{\substack{\text{Lower error} \\ \text{bound at step k}}} = \underbrace{\frac{\alpha}{1-\alpha}}_{\substack{\text{Discount factor} \\ \text{scaling}}} \underbrace{\min_{i=1,...,n} \{(T^kJ)(i) - (T^{k-1}J)(i)\}}_{\substack{\text{Minimum improvement} \\ \text{in value function}}} $$
  • Upper bound sequence:
$$ \underbrace{\bar{c}_k}_{\substack{\text{Upper error} \\ \text{bound at step k}}} = \underbrace{\frac{\alpha}{1-\alpha}}_{\substack{\text{Discount factor} \\ \text{scaling}}} \underbrace{\max_{i=1,...,n} \{(T^kJ)(i) - (T^{k-1}J)(i)\}}_{\substack{\text{Maximum improvement} \\ \text{in value function}}} $$

These bounds provide:

  • A sandwich theorem for the optimal value function
  • Computable error estimates during value iteration
  • Monotonically improving lower bounds
  • Monotonically decreasing upper bounds
  • Convergence guarantees based on the discount factor $\alpha$

In simple words, the value iteration algorithm works by:

  1. Starting with any bounded function $J$ as an initial estimate
  2. Repeatedly applying the Bellman operator $T$ to get better estimates:
    • $J_1 = TJ$
    • $J_2 = TJ_1 = T^2J$
    • $J_3 = TJ_2 = T^3J$ And so on…
  3. As we apply the operator more times ($N \to \infty$), our estimate converges to the optimal cost function $J^*$
  4. The error bounds above tell us exactly how close we are to $J^*$ at each iteration

This convergence is guaranteed by the contraction mapping property of the Bellman operator and the discount factor $\alpha < 1$.