Controlled Markov Chain (CMC)

  • A Controlled Markov Chain (CMC) is a stochastic process ${X_n}_{n \geq 0}$ that evolves over discrete time steps $n = 0, 1, 2, \ldots$.

  • At each time step $n$, the system is in a state $X_n$ belonging to a state space $S$. To influence the evolution of this process, we apply a control or action $Z_n$ from a set of feasible actions $A(X_n)$ that depends on the current state $X_n$. Thus, $Z_n \in A(X_n)$.

  • The defining characteristic of a Controlled Markov Chain is its transition probability, which satisfies the Markov property conditioned on the chosen action. Specifically, the probability of transitioning to a next state $X_{n+1} = j$ depends only on the current state $X_n = i$ and the action $Z_n = a$ taken at the current time step, and not on the history of states and actions. Mathematically, this is expressed as:

$$ P(X_{n+1} = j \mid X_n = i, Z_n = a, X_{n-1} = i_{n-1}, Z_{n-1} = a_{n-1}, \ldots, X_0 = i_0, Z_0 = a_0) = P(X_{n+1} = j \mid X_n = i, Z_n = a) $$

  • We denote the state transition probability as $p(i, a, j)$, which is the probability of transitioning from state $i$ to state $j$ when action $a$ is applied in state $i$:

$$ p(i, a, j) = P(X_{n+1} = j \mid X_n = i, Z_n = a) $$

Where:

  • $i, j \in S$ are states in the state space $S$.
  • $a \in A(i)$ is an action from the set of feasible actions $A(i)$ in state $i$.
  • $p(i, a, j)$ is a probability value, thus it satisfies:
    • $p(i, a, j) \geq 0$ for all states $i, j \in S$ and action $a \in A(i)$.
    • $\sum_{j \in S} p(i, a, j) = 1$ for all states $i \in S$ and action $a \in A(i)$. This ensures that for each state and action, the probabilities of transitioning to all possible next states sum up to 1.

Key Properties of Controlled Markov Chains:

  • Influence of Actions on Transitions: The transition probabilities $p(i, a, j)$ are explicitly dependent on the action $a$ chosen in the current state $i$. This is the “controlled” aspect, meaning our decisions directly influence how the system evolves. By selecting different actions in state $i$, we can alter the probabilities of transitioning to different next states $j$.

  • Markov Property: The future state $X_{n+1}$ is conditionally independent of the past states and actions given the current state $X_n$ and action $Z_n$. This property simplifies the analysis and prediction of the system’s future behavior, as we only need to know the present state and action to determine the probabilistic future. Intuitively, it means that all relevant information about the system’s history that affects its future is summarized in the current state.

  • Control via Action Sequence: The sequence of actions ${Z_n}_{n \geq 0}$ serves as the control input to the Markov chain. By carefully choosing these actions at each time step, we can guide the stochastic process towards desired outcomes. This is the foundation for decision-making and optimization problems in dynamic systems.

  • Framework for Sequential Decision Making: Controlled Markov Chains provide a rigorous mathematical framework for modeling systems where we make sequential decisions over time, and these decisions probabilistically affect the future states of the system. This is crucial for various applications, including robotics, economics, and operations research, where we need to plan a sequence of actions to achieve a goal in an uncertain environment.

In essence, a Controlled Markov Chain formalizes how a system evolves probabilistically over time under the influence of external controls or actions, adhering to the fundamental Markov property. This model is the basis for formulating and solving Markov Decision Processes, which aim to find optimal sequences of actions to optimize certain objectives.

Markov Decision Process (MDP)

A Markov Decision Process (MDP) is a mathematical framework for modeling sequential decision-making in stochastic environments. It extends the concept of a Controlled Markov Chain by incorporating a cost or reward structure associated with state transitions and actions.

Formal Definition:

An MDP is formally defined as a tuple $\mathcal{M} = (S, A, P, g)$, where:

  • $S$ is a set of states, representing all possible situations the system can be in. We assume $S$ is finite for simplicity, denoted as $S = {1, 2, \ldots, n}$.
  • $A$ is a set of actions, representing the decisions available to the agent. For each state $i \in S$, $A(i)$ denotes the set of actions available in state $i$. We assume each $A(i)$ is finite.
  • $P$ is the state transition probability function. For each state $i \in S$ and action $a \in A(i)$, $P(X_{n+1} = j \mid X_n = i, Z_n = a) = p(i, a, j)$ defines the probability of transitioning from state $i$ to state $j \in S$ when action $a$ is taken.
    • $p(i, a, j) \geq 0$ for all $i, j \in S, a \in A(i)$
    • $\sum_{j \in S} p(i, a, j) = 1$ for all $i \in S, a \in A(i)$
  • $g$ is the cost function. For each transition from state $i$ to state $j$ upon taking action $a \in A(i)$, $g(i, a, j)$ represents the immediate cost incurred.
    • $g(i, a, j)$ can also be interpreted as a negative reward. Minimizing cost is equivalent to maximizing reward.

Key Aspects of MDPs:

  • Controlled Markov Chain Foundation: MDPs inherit the properties of Controlled Markov Chains, particularly the Markov property, meaning future states depend only on the current state and action.
  • Cost/Reward Association: Each transition is associated with a cost (or reward), which is crucial for defining optimization problems.
  • Known Environment Dynamics: In the standard MDP framework, we assume the transition probabilities $p(i, a, j)$ and the cost function $g(i, a, j)$ are known. This is referred to as “model-based” reinforcement learning, where we have a model of the environment’s dynamics.
  • Objective of Optimal Actions: The fundamental goal in solving an MDP is to find a policy (a strategy for choosing actions in each state) that minimizes the expected cumulative cost (or maximizes the expected cumulative reward) over time. This policy dictates the agent’s behavior to achieve the desired objective in the stochastic environment.

Policy and Optimal Policy

Policy ($\pi$)

  • Definition: A policy $\pi$ is a strategy that dictates how an agent chooses actions in each state at each time step. For a finite horizon problem of length $N$, a policy is formally defined as a sequence of functions $\pi = {\mu_0, \mu_1, \ldots, \mu_{N-1}}$, where each function $\mu_k$ for time step $k \in {0, 1, \ldots, N-1}$ maps a state $s \in S$ to an action $a \in A(s)$.

    $$ \mu_k: S \rightarrow A $$ $$ \mu_k(s) \in A(s) \quad \forall s \in S, k \in {0, 1, \ldots, N-1} $$

  • Explanation: Intuitively, a policy $\pi$ is a set of rules, one for each time step, that tells the agent which action to take when it is in a particular state. The policy completely determines the agent’s behavior throughout the decision-making process. In essence, it is the “brain” of the agent, guiding its actions in every possible situation.

Optimal Policy ($\pi^*$)

  • Definition: An optimal policy $\pi^*$ is a policy that minimizes the expected total cost over the entire planning horizon. To define this formally, let $J_N(x_0)$ be the expected total cost when starting from an initial state $x_0$ and following a policy $\pi = {\mu_0, \mu_1, \ldots, \mu_{N-1}}$. For a finite horizon $N$, the cost-to-go function $J_\pi(x_0)$ under policy $\pi$ is given by:

    $$ J_\pi(x_0) = E\left[g_N(x_N) + \sum_{k=0}^{N-1} g(x_k,\mu_k(x_k),x_{k+1}) \mid x_0 = x_0\right] $$

    where:

    • $x_0$ is the initial state at time $t=0$.
    • $x_k$ is the state at time $k$.
    • $x_{k+1}$ is the state at time $k+1$.
    • $\mu_k(x_k)$ is the action taken at time $k$ in state $x_k$ according to policy $\pi$.
    • $g(x_k,\mu_k(x_k),x_{k+1})$ is the immediate cost incurred when transitioning from state $x_k$ to $x_{k+1}$ by taking action $\mu_k(x_k)$.
    • $g_N(x_N)$ is the terminal cost at the final state $x_N$ at time $N$.
    • The expectation $E[\cdot \mid x_0 = x_0]$ is taken over the stochastic transitions of states $x_1, x_2, \ldots, x_N$, which are determined by the policy $\pi$ and the transition probabilities of the MDP.

    An optimal policy $\pi^$ is then defined as any policy that achieves the minimum possible expected cost for all starting states $x_0 \in S$. Let $\Pi$ be the set of all possible policies. The optimal cost-to-go function $J^_N(x_0)$ is given by:

    $$ J^*N(x_0) = \min{\pi \in \Pi} J_{\pi}(x_0) \quad \forall x_0 \in S $$

    and the set of optimal policies $\pi^*$ is the set of policies that achieve this minimum cost:

    $$ \pi^* = {\pi \in \Pi \mid J_{\pi}(x_0) = J^*_N(x_0) \quad \forall x_0 \in S } $$

  • Explanation of Cost-to-go Function $J_N(x_0)$: The cost-to-go function $J_\pi(x_0)$ (or $J^_N(x_0)$ for the optimal policy) represents the total expected cost an agent will accumulate from the initial state $x_0$ until the end of the planning horizon, when following policy $\pi$ (or the optimal policy $\pi^$). It serves as:

    • A predictive measure: It quantifies the expected future cost associated with starting in state $x_0$ and acting according to a given policy.
    • A recursive value: It inherently incorporates both the immediate costs incurred at each step and the expected future costs from subsequent states. This recursive nature is fundamental to dynamic programming approaches for solving MDPs.
    • A basis for optimization: By comparing the cost-to-go functions of different policies, we can identify policies that lead to lower expected costs, ultimately aiming to find the optimal policy $\pi^*$ that minimizes this function for all starting states.

  • Note: It is important to note that there might be multiple optimal policies that all achieve the same minimal expected cost. The definition of $\pi^*$ encompasses all such policies. The goal of solving an MDP is to find at least one optimal policy.

Principle of Optimality

  • Definition: The Principle of Optimality is a foundational concept in dynamic programming. It asserts that an optimal policy is composed of optimal sub-policies. In simpler terms, if you are on an optimal path from the start to the end, then every segment of that path must also be optimal for the corresponding subproblem.

  • Intuitive Explanation: Imagine you are planning the fastest route from city A to city C, passing through city B. If you have found the overall fastest route from A to C, then the segment of your route from B to C must also be the fastest route from B to C, regardless of how you arrived at B. The Principle of Optimality guarantees that optimal decisions are independent of “irrelevant” history, focusing only on the current state and future costs.

  • Formal Statement: Let $\pi^* = {\mu_0^, \mu_1^, \ldots, \mu_{N-1}^}$ be an optimal policy for the entire finite-horizon problem (from time 0 to $N-1$). Suppose that when following $\pi^$, the system reaches state $x_i$ at time step $i$ with a non-zero probability. Consider a subproblem that starts at time step $i$ in state $x_i$ and continues until the end of the horizon $N-1$. The Principle of Optimality states that the “tail” or truncated policy $\pi_i^* = {\mu_i^, \mu_{i+1}^, \ldots, \mu_{N-1}^}$, which consists of the remaining decisions of $\pi^$ from time $i$ onwards, must be an optimal policy for this subproblem.

    Mathematically, for any time step $i \in {0, 1, \ldots, N-1}$ and any state $x_i$ reachable with positive probability under $\pi^*$, the following holds:

    Consider the subproblem starting from state $x_i$ at time $i$:

    $$ \min_{{\underbrace{\mu_i, \mu_{i+1}, \ldots, \mu_{N-1}}{\text{sequence of decision rules}}}} E\left[\underbrace{g_N(x_N)}{\text{terminal cost}} + \sum_{k=i}^{N-1} \underbrace{g(x_k, \mu_k(x_k), x_{k+1})}{\text{stage cost at time k}} \mid \underbrace{x_i = x_i}{\text{initial condition}} \right] $$

    The truncated policy $\pi_i^* = {\mu_i^, \mu_{i+1}^, \ldots, \mu_{N-1}^}$ is an optimal policy for this subproblem. This means that applying $\pi_i^$ from state $x_i$ onwards will achieve the minimum expected cost for the remaining stages.

  • Breakdown of the Formal Statement:

    • Optimal Policy $\pi^ = {\mu_0^, \mu_1^, \ldots, \mu_{N-1}^*}$*: This represents the sequence of optimal decision rules for the entire problem from time 0 to $N-1$.
    • Truncated Policy $\pi_i^ = {\mu_i^, \mu_{i+1}^, \ldots, \mu_{N-1}^*}$*: This is the part of the optimal policy that applies from time step $i$ onwards.
    • Subproblem starting in state $x_i$ at time $i$: We are considering a new problem that begins at time $i$ in a specific state $x_i$.
    • $\min_{{\mu_i, \mu_{i+1}, \ldots, \mu_{N-1}}} E\left[g_N(x_N) + \sum_{k=i}^{N-1} g(x_k, \mu_k(x_k), x_{k+1}) \mid x_i = x_i \right]$: This expression represents the minimization of the expected total cost for the subproblem, starting from time $i$ in state $x_i$. We are minimizing over all possible policies ${\mu_i, \mu_{i+1}, \ldots, \mu_{N-1}}$ for the remaining time steps.
    • Optimality of $\pi_i^*$ for the subproblem: The principle states that the truncated policy $\pi_i^*$ is one of the policies that achieves this minimum expected cost for the subproblem.

  • Key Implications:

    • Optimal Substructure: Optimal solutions are built from optimal solutions to subproblems. This is the core idea, meaning that to solve the overall problem optimally, we need to solve its subproblems optimally.
    • Decomposition of Complexity: The principle allows us to break down a complex, multi-stage decision problem into a sequence of simpler, single-stage decision problems. This divide-and-conquer approach is crucial for managing complexity.
    • Foundation for Dynamic Programming: The Principle of Optimality is the bedrock upon which dynamic programming algorithms are built. It justifies the recursive approach of dynamic programming, where we solve problems by combining solutions to overlapping subproblems.
    • Recursive Solution Approach: It enables solving problems recursively, typically working backwards in time. We start by solving the “last stage” subproblems and then use these solutions to solve subproblems at earlier stages, eventually reaching the initial stage and solving the original problem.

Dynamic Programming

Dynamic Programming (DP) is a systematic method for solving optimal control problems by utilizing the Principle of Optimality. It operates by working backward in time, from the final stage to the initial stage, to find the optimal policy and the optimal cost-to-go function.

At the heart of Dynamic Programming is the recursive application of Bellman’s equation. For a finite-horizon problem spanning $N$ stages, the algorithm is defined by the following recursive relations:

  1. Base Case: Terminal Stage Cost At the final stage $N$, no further decisions are required. The cost incurred is simply the terminal cost $g_N(x_N)$. The optimal cost-to-go at the terminal stage is thus initialized as: $$J_N(x_N) = g_N(x_N)$$

    • Explanation: $$ \underbrace{J_N(x_N)}{\substack{\text{Optimal cost-to-go} \ \text{at stage } N \text{ from state } x_N}} = \underbrace{g_N(x_N)}{\substack{\text{Terminal cost} \ \text{at stage } N \text{ for state } x_N}} $$ This base case initiates the backward recursion. Since stage $N$ is the end of the horizon, the cost-to-go from this stage is solely determined by the terminal cost $g_N(x_N)$.

  2. Recursive Step: Bellman Equation for Stages $k = N-1, N-2, \ldots, 0$ For each stage $k$ from $N-1$ down to $0$, and for every possible state $x_k$, the optimal cost-to-go $J_k(x_k)$ is computed by minimizing over all feasible actions $a_k \in A(x_k)$ the sum of the immediate stage cost and the expected optimal cost-to-go from the succeeding stage. This is mathematically represented as: $$J_k(x_k) = \min_{a_k \in A(x_k)} E_{x_{k+1}}\left[g_k(x_k,a_k,x_{k+1}) + J_{k+1}(x_{k+1}) \mid x_k, a_k \right]$$

    • Explanation: $$ \underbrace{J_k(x_k)}{\substack{\text{Optimal cost-to-go} \ \text{at stage } k \text{ from state } x_k}} = \min{a_k \in A(x_k)} \underbrace{E_{x_{k+1}} \left[ \underbrace{g_k(x_k,a_k,x_{k+1})}{\substack{\text{Immediate stage cost} \ \text{at stage } k}} + \underbrace{J{k+1}(x_{k+1})}{\substack{\text{Optimal cost-to-go} \ \text{from stage } k+1}} \biggm\vert x_k, a_k \right]}{\substack{\text{Expected total cost} \ \text{from stage } k \text{ onwards}}} $$ Where:
      • $J_k(x_k)$: Optimal cost-to-go function at stage $k$ for state $x_k$. It represents the minimum expected total cost from stage $k$ to the final stage $N$, starting from state $x_k$.
      • $A(x_k)$: Set of admissible actions in state $x_k$.
      • $E_{x_{k+1}}[\cdot \mid x_k, a_k]$: Expectation operator with respect to the next state $x_{k+1}$, conditioned on the current state $x_k$ and action $a_k$. This expectation is calculated using the state transition probabilities $P(x_{k+1} | x_k, a_k)$.
      • $g_k(x_k, a_k, x_{k+1})$: Stage cost incurred at stage $k$ for transitioning from state $x_k$ to $x_{k+1}$ when action $a_k$ is chosen.
      • $J_{k+1}(x_{k+1})$: Optimal cost-to-go from state $x_{k+1}$ at the next stage $k+1$. This value is assumed to be already computed from the backward recursion.
      • $\min_{a_k \in A(x_k)}$: Minimization operation over all possible actions $a_k$ in state $x_k$. For each state $x_k$, we evaluate the expected total cost for every possible action $a_k$ and select the action that yields the minimum expected cost. This minimum cost is then assigned as $J_k(x_k)$.

  3. Optimal Policy Extraction $\mu_k^*(x_k)$ at each stage $k$ The optimal policy $\mu_k^(x_k)$ at each stage $k$ for a given state $x_k$ is the action that achieves the minimum value in Bellman’s equation. It is determined by: $$\mu_k^(x_k) = \arg\min_{a_k \in A(x_k)} E_{x_{k+1}}\left[g_k(x_k,a_k,x_{k+1}) + J_{k+1}(x_{k+1}) \mid x_k, a_k \right]$$

    • Explanation: $$ \underbrace{\mu_k^*(x_k)}{\substack{\text{Optimal policy} \ \text{at stage } k \text{ for state } x_k}} = \arg\min{a_k \in A(x_k)} \underbrace{E_{x_{k+1}} \left[ \underbrace{g_k(x_k,a_k,x_{k+1})}{\substack{\text{Immediate stage cost} \ \text{at stage } k}} + \underbrace{J{k+1}(x_{k+1})}{\substack{\text{Optimal cost-to-go} \ \text{from stage } k+1}} \biggm\vert x_k, a_k \right]}{\substack{\text{Expected total cost} \ \text{from stage } k \text{ onwards}}} $$ Where:
      • $\mu_k^*(x_k)$: Optimal action (policy) to be taken in state $x_k$ at stage $k$. This defines the optimal decision rule at stage $k$.
      • $\arg\min_{a_k \in A(x_k)}$: Argument of the minimum operator. It selects the action $a_k$ from the set of admissible actions $A(x_k)$ that minimizes the expected total cost. If multiple actions result in the same minimum expected cost, any of them can be chosen as the optimal action.

Key Characteristics of Dynamic Programming Algorithm:

  • Backward Recursion:

    • DP initiates computations from the terminal stage $N$ because the optimal cost at the final stage is readily known (terminal cost). Subsequently, it recursively calculates the optimal cost-to-go functions and optimal policies for preceding stages, progressing backward towards the initial stage. This backward approach is crucial as the optimal decision at each stage is contingent upon the optimal decisions at future stages, as dictated by the Principle of Optimality.

  • Optimal Cost-to-Go Function Computation:

    • The algorithm computes $J_k(x_k)$, representing the minimum expected cost from stage $k$ to the end of the horizon, starting from state $x_k$. By computing $J_k(x_k)$ for all stages $k$ and all states $x_k$, DP provides a comprehensive mapping of optimal costs from any point in time and state space to the end of the problem.

  • Optimal Policy Determination:

    • For each stage $k$ and each state $x_k$, the algorithm determines the optimal action $\mu_k^(x_k)$ that minimizes the expected cost-to-go. The collection of these optimal decision rules ${\mu_0^, \mu_1^, \ldots, \mu_{N-1}^}$ constitutes the optimal policy for the entire finite-horizon problem.

  • Guarantee of Global Optimality:

    • By systematically evaluating all feasible actions at each stage and making decisions based on minimizing the expected future costs (which are themselves optimally computed), Dynamic Programming ensures that the resulting policy is globally optimal. This guarantee stems directly from the Principle of Optimality, which ensures that a sequence of locally optimal decisions leads to overall optimality for the entire problem.

By adhering to these steps, Dynamic Programming provides an efficient methodology to solve complex sequential decision-making problems by decomposing them into simpler, overlapping subproblems and solving them in a structured, recursive manner.

  • Guarantees Global Optimality through Recursive Optimization:
    • By systematically exploring all possible actions at each stage and making decisions based on minimizing the expected future costs (which are themselves optimally computed), dynamic programming guarantees that the resulting policy is globally optimal. This is a direct consequence of the Principle of Optimality, which ensures that by making locally optimal decisions at each stage, we achieve overall optimality for the entire problem.

By following these steps, dynamic programming efficiently solves complex sequential decision-making problems by breaking them down into simpler, overlapping subproblems and solving them in a structured, recursive manner.