TensorWrites
← Writing library

Finite Markov Decision Processes - Sequential Decision Making

Introduction to sequential decision-making in reinforcement learning, including agent–environment interaction, rewards, returns, value functions, and Bellman equations with intuitive example.

14 min readShanmukha Sainath
On this page · 23 sections
HeaderAn illustration of Finite MDP

This post captures my takeaways from Chapter 3 of the book Reinforcement Learning: An Introduction by Sutton and Barto, the bible of RL.

The Setup : Agent and Environment

Recap from Intro to RL and Multi-Armed Bandits, we have seen that agent, a learner and decision maker interacts with an environment. At each step, the agent observes the state of the environment and takes an action. The environment then transitions to a new state and provides a reward to the agent. Agent seeks to maximize the rewards it receives over time by selecting optimal actions. Markov Decision Process (MDP) is a mathematical framework for modeling such interactions in RL.

Interaction between Agent and EnvironmentInteraction between Agent and Environment in a MDP

The continuous interactions described in above figure results in sequence of observations, actions and rewards:

S0,A0,R1,S1,A1,R2,S2,A2,R3,...S_0, A_0, R_1, S_1, A_1, R_2, S_2, A_2, R_3, ...
Sequence of observations, actions and rewards

In a finite MDP, the state, action and rewards have finite number of elements. Let's denote the set of states by S\mathcal{S}, actions by A\mathcal{A}, and rewards by R\mathcal{R}. The random variables St,At,Rt+1S_t, A_t, R_{t+1} are probability distributions dependent on previous state and action.

p(s′,r∣s,a)=P(St=s′,Rt=r∣St−1=s,At−1=a)∑s′∈S∑r∈Rp(s′,r∣s,a)=1, for all s∈S,a∈A(s)p(s', r | s, a) = P(S_{t} = s', R_{t} = r | S_{t-1} = s, A_{t-1} = a) \\ \\[15pt] \sum_{s' \in \mathcal{S}} \sum_{r \in \mathcal{R}} p(s', r | s, a) = 1, \text{ for all } s \in \mathcal{S}, a \in \mathcal{A}(s)
Probability distribution of next state and reward

When is it a MDP?

The function pp completely defines the dynamics of MDP. In MDP, the StS_t and RtR_t only depends on St−1S_{t-1} and At−1A_{t-1} and not on any previous states and actions. The state must contain all the past agent-environment interactions information. The state that follows this is said to have the Markov Property. Using the above equation we can formalize any information that we would like to know about the environment:

State Transition Probabilities

p(s′∣s,a)=P(St=s′∣St−1=s,At−1=a)=∑r∈Rp(s′,r∣s,a)p(s' | s, a) = P(S_{t} = s' | S_{t-1} = s, A_{t-1} = a) = \sum_{r \in \mathcal{R}} p(s', r | s, a)
State transition probabilities

Expected Rewards

State-Action pairs

r(s,a)=E[Rt∣St−1=s,At−1=a]=∑r∈Rr∑s′∈Sp(s′,r∣s,a)r(s, a) = E[R_{t} | S_{t-1} = s, A_{t-1} = a] = \sum_{r \in \mathcal{R}} r \sum_{s' \in \mathcal{S}} p(s', r | s, a)
Expected rewards for state-action pairs

State-Action-Next State tuples

r(s,a,s′)=E[Rt∣St−1=s,At−1=a,St=s′]=∑r∈Rrp(s′,r∣s,a)p(s′∣s,a)r(s, a, s') = E[R_{t} | S_{t-1} = s, A_{t-1} = a, S_t = s'] = \sum_{r \in \mathcal{R}} r \frac{p(s', r | s, a)}{p(s' | s, a)}
Expected rewards for state-action-next_state tuples

I encourage you to deduce the above equations and generate more such formulations you can think of. For example, what is the expected reward for a state-action-next_state-reward tuple? Go through Chain rule and bayes theorem to understand the above equations in-depth.

Applications

MDP framework is flexible and can be applied to a wide range of problems. Time-steps need not be a fixed intervals of time, it can refer to any successive stages of interaction between agent and environment. The actions can be as simple as the voltage control in robot arm to as complex as the stock trading decisions. The states can be as simple as the position of the robot arm to as complex as the current market conditions. In general actions can be any decisions we want to learn how to make and state can be anything that helps us make those decisions.

The boundary between agent and environment is also not rigid. For example, in a robot arm problem, the motor control system can be considered part of the environment or part of the agent. In general anything that is not in our control is environment. The agent-environment boundary only signifies the limit og agent's control, not of it's knowledge. Reward computation is considered to be external to the agent, because it defines the task to the agent and agent should not have control over it.

MDP framework is a very powerful yet simple abstraction of goal directed learning which reduces the problem into three signals passing back and forth between agent and environment: State, Action and Reward.

The Payoff : Goals and Rewards

The agent's goal is to maximize cumulative reward in long run, which is called as reward hypothesis. This idea of formalizing goal by using rewards is a very distincitive feature of reinforcement learning. The definition of reward signal should be indicative of what we want the agent to achieve and any prior knowledge about how to achieve the goal should not be imparted on agent.

The reward signal is a way of communicating what we want to achieve and not how to achieve it.

The Timeline : Returns and Episodes

A simple way to define the cumulative reward is to sum up all the rewards the agent receives over time. This approach makes sense for tasks that have a clear start and end which are called as episodes and the tasks as episodic tasks. Each episode ends in a special state called as terminal state. Every episode begins independently of the previous episodes and the agent starts from the same initial state. The time of termination T varies from episode to episode.

Gt=Rt+1+Rt+2+...+RTG_t = R_{t+1} + R_{t+2} + ... + R_T
Cumulative reward

The tasks which do not have a naturally identifiable episodes are called as continuing tasks. The above formula if used here will result in infinite sum. To avoid this we introduce a discount factor γ∈[0,1]\gamma \in [0, 1] which is a factor by which we discount the future rewards. This concept is called as discounting. A reward recieved k time steps in future is worth only γk−1\gamma^{k-1} times if it's recieved immediately. The special case of γ=0\gamma = 0 makes the agent myopic, only caring about immediate rewards. The special case of γ=1\gamma = 1 makes the agent far-sighted, caring about all the future rewards equally.

Gt=Rt+1+γRt+2+γ2Rt+3+...+γT−t−1RTGt=Rt+1+γGt+1G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... + \gamma^{T-t-1} R_T \\[15pt] G_t = R_{t+1} + \gamma G_{t+1}
Discounted cumulative reward

The Bridge : Unified Notation for Episodic and Continuous tasks

In episodic tasks, every episode starts with a time step of zero. So, it becomes essential to track the episode number along with the time step (StS_t as St,iS_{t,i}). But when we disucss about episodic tasks, we always talk or think about a single episode, which makes the notation St,iS_{t,i} redundant.

One more thing to note is about infinite time steps in continuous tasks. To unify both episodic and continuous tasks, we introduce a special episode called absorbing state for episodic tasks. This state transitions to itself and has zero reward.

Absorbing StateEpisodic Task with absorbing state

The generalized return for both episodic and continuous tasks is given by (handles T=∞T = \infty or γ=1\gamma = 1 cases but not both):

Gt=∑k=t+1Tγk−t−1RkG_t = \sum_{k=t+1}^{T} \gamma^{k-t-1} R_k
Generalized return for both episodic and continuous tasks

The Strategy : Policy and Value functions

  • Value Function: Estimates how good it is to be in a state or take an action in a state. "How good" is measured by the expected return that is discussed in the previous section.
  • Policy: A policy is a function that assigns to each state the probability of choosing each available action. It determines how the agent behaves at a particular moment, and value functions are defined in relation to these specific policies. Let agent follows a policy π\pi at time tt, then the probability of choosing action aa in state ss is given by π(a∣s)\pi(a|s) - Probability that At=aA_t = a given St=sS_{t} = s.

State-Value Function

The value function of a state ss under a policy π\pi denotes as vπ(s)v_\pi(s) is the expected return starting from state ss and following policy π\pi thereafter. This is also called as state-value function for policy π\pi.

vπ(s)=Eπ[Gt∣St=s]v_\pi(s) = E_\pi[G_t | S_t = s]
State-Value function

Action-Value Function

The value of taking an action aa in a state ss under a policy π\pi denotes as qπ(s,a)q_\pi(s, a) is defined as action-value function for policy π\pi.

qπ(s,a)=Eπ[Gt∣St=s,At=a]q_\pi(s, a) = E_\pi[G_t | S_t = s, A_t = a]
Action-Value function

Bellman Equation

The value functions vπv_\pi and qπq_\pi are computed from experience i.e, if an agent follows a certain policy π\pi and keeps track of the returns folllowed by every state encountered, the state's value vπ(s)v_\pi(s) for every state as we iterate infinite times. Similarly, if separate averages are tracked for each state-action pair, they will converge to qπ(s,a)q_\pi(s, a) for every state-action pair. This method is called as Monte Carlo method (Next chapter).

This method is intangible when there are many states and actions where keeping track of all the averages is almost impossible. In such cases, we parametrize the vπv_\pi and qπq_\pi functions and adjust parameters to match the actual returns (not discussed in this post).

Value functions follows recursive relationships. For any policy π\pi, the value of a state ss can be written in terms of value of its successor states.

vπ(s)=Eπ[Gt∣St=s]vπ(s)=Eπ[Rt+1+γGt+1∣St=s]vπ(s)=∑a∈Aπ(a∣s)∑s′∈S∑r∈Rp(s′,r∣s,a)[r+γEπ[Gt+1∣St+1=s′]]vπ(s)=∑a∈Aπ(a∣s)∑s′∈S,r∈Rp(s′,r∣s,a)[r+γvπ(s′)]v_\pi(s) = E_\pi[G_t | S_t = s] \\[15pt] v_\pi(s) = E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s] \\[15pt] v_\pi(s) = \sum_{a \in A} \pi(a|s) \sum_{s' \in S}\sum_{r \in R} p(s', r | s, a) [r + \gamma E_\pi[G_{t+1} | S_{t+1} = s']] \\[15pt] v_\pi(s) = \sum_{a \in A} \pi(a|s) \sum_{s' \in S, r \in R} p(s', r | s, a) [r + \gamma v_\pi(s')]
Deducing Bellman equation

The last equation is called as Bellman equation. It is sum over all possible actions the agent can take, and for each action, it is sum over all possible next states and rewards the agent can receive. For each triple, we compute the probability term π(a∣s)p(s′,r∣s,a)\pi(a|s) p(s', r | s, a) and multiply it with the reward term r+γvπ(s′)r + \gamma v_\pi(s'). This is represented as a backup diagram below. The backup operations transfers the value of successor states to the current state. These backup diagrams are used in many RL algorithms to provide visual intuition about the algorithm.

Backup DiagramBackup diagram for vπv_\pi Backup DiagramBackup diagram for qπq_\pi

Below backup diagrams shows the dependencies between state-value and action-value functions.

  • Top: The value of a state dependes on the values of actions possible from that state and how likely each action can be taken under current policy.
  • Bottom: The value of an action depends on the expected next rewards and sum of remaining rewards.
Backup DiagramBackup diagrams for sta-value and action-value dependencies

The Solution : Optimal Policy and Value functions

A policy π\pi is said to be better than policy π′\pi' if it's expected return is greater than or equal for all states (π≥π′\pi \geq \pi' iff vπ(s)≥vπ′(s)v_\pi(s) \geq v_{\pi'}(s) for all s∈Ss \in S). The policy which is better than all other policies is called as optimal policy and is denoted by π∗\pi_*. This optimal policy π∗\pi_* results in optimal state-value function v∗v_* and optimal action-value function q∗q_* and their Bellman optimal equations are:

v∗(s)=max⁡πvπ(s)=max⁡a∑s′,rp(s′,r∣s,a)[r+γv∗(s′)]q∗(s,a)=max⁡πqπ(s,a)=∑s′,rp(s′,r∣s,a)[r+γq∗(s′,a′)]v_*(s) = \max_\pi v_\pi(s) = \max_a \sum_{s', r} p(s', r | s, a) [r + \gamma v_*(s')] \\[15pt] q_*(s, a) = \max_\pi q_\pi(s, a) = \sum_{s', r} p(s', r | s, a) [r + \gamma q_*(s', a')]
Optimal state-value and action-value functions
Backup Diagram OptimalBackup diagram for v∗v_* and q∗q_*

For a finite MDP, the Bellman optimality equation for v∗v_* has unique solution. It is a system of equations, one for each state. If the the dynamics of environment (pp) are known, then the optimal value function v∗v_* is obtained by solving system of non-linear equations.

Using v∗v_* we can find the optimal policy π∗\pi_* by choosing the action that maximizes the expected return for each state. A one-step search is performed to find the optimal policy. If we have q∗q_* then the optimal policy calculation doesn't require one step search as we cache the values of q∗q_* for each state-action pair. Hence, using q∗q_*, the optimal policy can be obtained without knowing about possible next states and rewards (but at the expense of representing as a function of state-action pairs).

π∗(s)=arg⁡max⁡a∑s′,rp(s′,r∣s,a)[r+γv∗(s′)]\pi_*(s) = \arg\max_a \sum_{s', r} p(s', r | s, a) [r + \gamma v_*(s')]
Optimal policy

Limitations

The above proposed method can only be used when:

  • The dynamics of the enviuronment are accurately known
  • Computational resources are available to solve the system of equations
  • The states have the Markov property

Any real-case scenario violates at least one of the above conditions. For instance, in a chess game, the number of states is too large to be performing a exhaustive search looking ahead all the possible moves and their feasibilities alongwith rewards. So, we generally settle at approximate solutions of Bellman optimality equations (actual solutions are out of scope of this blog).

Example : Warehouse Navigation Robot

Setup

The agent (robot) is placed in a warehouse represented as a grid with a goal to reach the target location. At each step, the agent can move in four directions (up, down, left, right) and the goal is to reach the shipping bay to deliver the package with minimum number of steps.

Warehouse EnvironmentWarehouse environment
  • States (SS): Coordinates (x,y)(x, y) where x,y∈{0,1,2}x, y \in \{0, 1, 2\}.
  • Actions (AA): {North, South, East, West}\{\text{North, South, East, West}\}.
  • Rewards (RR):
    • -1 for every standard movement.
    • +10 for reaching the Shipping Bay at (2,2)(2, 2) (Terminal State).
    • Congestion Penalty: Moving into or through state (1,1)(1, 1) is risky.
  • Dynamics (pp):
    • In congested aisle (1,1)(1, 1),
      • Success (60%): The aisle is clear. It reaches (1,1)(1, 1) with r=−1r = -1.
      • Failuere (40%): A pallet blocks the path. The robot stays at (1,0)(1, 0) and receives r=−1r = -1.
    • In other aisles, the agent has 100% chance of moving in the desired direction.
    • Agent can move in any direction with equal probability (1/4).

Return

A discount rate of γ=0.9\gamma = 0.9 is used to discount future rewards. Consider a trajectory where the robot attempts to enter the congested aisle, gets blocked once, succeeds on the second try, and then reaches the goal.

The Trajectory: S0:(1,0)→A0:ER1:−1,S1:(1,0)→A1:ER2:−1,S2:(1,1)→A2:ER3:−1,S3:(1,2)…S_0: (1,0) \xrightarrow{A_0: \text{E}} R_1: -1, S_1: (1,0) \xrightarrow{A_1: \text{E}} R_2: -1, S_2: (1,1) \xrightarrow{A_2: \text{E}} R_3: -1, S_3: (1,2) \dots (reaches goal at T=4T=4).

The Calculation:

G0=R1+γR2+γ2R3+γ3R4G0=−1+0.9(−1)+0.81(−1)+0.729(10)G0=−1−0.9−0.81+7.29=4.58G_0 = R_1 + \gamma R_2 + \gamma^2 R_3 + \gamma^3 R_4 \\[15pt] G_0 = -1 + 0.9(-1) + 0.81(-1) + 0.729(10) \\[15pt] G_0 = -1 - 0.9 - 0.81 + 7.29 = \mathbf{4.58}

Bellman Equation

We want to find the value of the state (1,0)(1,0) under a policy π\pi where the robot always chooses to go East. Assume the neighboring state values are already known: vπ(1,1)=6.0v_\pi(1,1) = 6.0 and vπ(1,0)=1.5v_\pi(1,0) = 1.5.

Applying the Equation:

vπ(1,0)=∑s′,rp(s′,r∣(1,0),East)[r+γvπ(s′)]vπ(1,0)=0.6[−1+0.9(6.0)]+0.4[−1+0.9(1.5)]vπ(1,0)=0.6[4.4]+0.4[0.35]vπ(1,0)=2.64+0.14=2.78v_\pi(1,0) = \sum_{s', r} p(s', r | (1,0), \text{East}) [r + \gamma v_\pi(s')] \\[15pt] v_\pi(1,0) = 0.6[-1 + 0.9(6.0)] + 0.4[-1 + 0.9(1.5)] \\[15pt] v_\pi(1,0) = 0.6[4.4] + 0.4[0.35] \\[15pt] v_\pi(1,0) = 2.64 + 0.14 = \mathbf{2.78}

Optimal Policy

The optimal policy π∗\pi_* is found by comparing the values of all possible actions. At state (1,0)(1,0), the agent compares the value of the "Congested Shortcut" vs. the "Clear Long Way."

v∗(1,0)=max⁡{q∗((1,0),East) [Congested]q∗((1,0),North) [Clear Path]}v_*(1,0) = \max \left\{ \begin{array}{l} q_*( (1,0), \text{East} ) \text{ [Congested]} \\ q_*( (1,0), \text{North} ) \text{ [Clear Path]} \end{array} \right\}

If the q∗q_* value of going North (avoiding the crowd) is 3.53.5 and the q∗q_* value of pushing through the East aisle is 2.782.78, the Optimal Policy π∗(1,0)\pi_*(1,0) will deterministically choose North, even though it increases the physical distance to the goal.

References

  1. Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction.

Tools

  • Image Generation: Gemini, ChatGPT
  • Editor: Antigravity
  • Flowchart and Diagrams: Excalidraw, Slides

Citation

Cited as:

Shanmukha Sainath. "Finite Markov Decision Processes - Sequential Decision Making". TensorWrites (Feb 2026). https://www.tensorwrites.com/posts/finite-mdp

BibTeX:
@article{finitemdp2026,
  title   = "Finite Markov Decision Processes - Sequential Decision Making",
  author  = "Shanmukha Sainath",
  journal = "TensorWrites",
  year    = "2026",
  month   = "Feb",
  url     = "https://www.tensorwrites.com/posts/finite-mdp"
}