A captain who cannot rewind the innings
Over 18 of a T20 run chase. The chasing team needs 42 runs from 12 balls with 4 wickets in hand. The batting captain has exactly one decision to make right now: send the next batter out to attack every ball, or consolidate and rotate strike, banking on the required rate staying reachable. Whatever the captain decides, the bowler responds, the ball is bowled, runs are scored (or a wicket falls), and a new situation appears: fewer overs, a possibly different required rate, possibly one fewer wicket. The captain then decides again, from this new situation, not from the situation two overs ago. There is no rewind button. Every decision is made once, under uncertainty, and the game moves on to a new state shaped by that decision.
This is the shape of every problem this chapter is about: an agent makes a decision, the world responds stochastically, a new situation results, and the agent decides again. Route planning for a delivery fleet under changing traffic, inventory reordering under uncertain demand, an ISRO orbital insertion sequence under thruster uncertainty, a game-playing program choosing its next move: all of these share the same skeleton as the run chase. The mathematical object that captures that skeleton precisely is the Markov Decision Process, or MDP. It is the formal foundation on which the rest of reinforcement learning (Q-learning, policy gradients, actor-critic methods) is built. Before any of those algorithms make sense, the object they operate on has to be defined exactly.
From decision problem to formal object: the MDP tuple
Strip the cricket story down to its moving parts. At each discrete time step t, the world is in some state s_t. The agent picks an action a_t from the actions available in that state. The world then transitions to a new state s_{t+1}, and the agent receives a numerical reward r_{t+1}. This repeats. An MDP formalizes this as a 5-tuple (S, A, P, R, γ):
S, the state space: every distinct situation the agent can find itself in. In the run chase, a natural (if coarse) state is a summary of match position, for instance (overs remaining, wickets remaining, runs still needed). A, the action space: the choices available in a given state, here {Attack, Consolidate}. P(s' | s, a), the transition function: the probability that taking action a in state s lands the process in state s'. This is where uncertainty enters; attacking does not deterministically produce a good outcome, it shifts the odds. R(s, a), the reward function: the immediate numerical payoff for taking action a in state s (here, something like runs scored above or below the required rate that over). γ (gamma), the discount factor, a number in [0, 1) that controls how much the agent should value a rupee of reward now versus a rupee of reward several overs from now.
Nothing here is specific to cricket. Swap in (fleet location, remaining battery, order queue) for state and (route A, route B) for action, and the same five objects describe a delivery-routing MDP. The tuple is the general template; the run chase is one instantiation of it, used throughout this chapter because its numbers are small enough to compute by hand.
Why "Markov"? The property that makes this tractable
The transition function is written P(s' | s, a), not P(s' | s_t, a_t, s_{t-1}, a_{t-1}, s_{t-2}, ...). That is the entire content of the Markov property: the probability of the next state depends only on the current state and action, not on the full history of how the process arrived there. Formally, for any sequence of states and actions,
P(s_{t+1} | s_t, a_t, s_{t-1}, a_{t-1}, ..., s_0, a_0) = P(s_{t+1} | s_t, a_t)
This single assumption is what makes the problem computationally tractable. Without it, an optimal decision at over 18 might in principle depend on every ball bowled since over 1, and the state space needed to represent "everything that happened so far" would explode combinatorially. With it, the current state is a complete summary of everything the agent needs to decide optimally. The captain does not need to recall exactly which overs produced which scores; the current tally of (overs left, wickets left, runs needed) is enough.
Misconception, named and corrected: students meeting this for the first time often read the Markov property as a claim about reality: "the game has no memory," or "what happened three overs ago genuinely has zero effect on what happens next." That is false, and it is not what the property says. Cricket momentum is real; a batter who has just middled three boundaries plausibly has a different chance of continuing to score than one who has just been beaten twice outside off. The Markov property is not a fact you discover about the world, it is a modeling choice you make when you define the state. If recent momentum genuinely affects future transitions, the fix is not to abandon the MDP framework, it is to enrich the state so that it includes momentum: for example, redefine the state to include "runs scored in the last two overs" as a component. Once the state is defined richly enough to be a sufficient statistic for everything decision-relevant about the history, the Markov property holds by construction, because you built the state to make it hold. The property is a design target for the state representation, not a restriction on what kinds of processes can be modeled. Any process can be made Markov by folding enough history into the state; the real engineering question is always how much history is actually necessary before adding more stops changing the optimal decision.
Policies, value functions, and the Bellman equation
A policy π is the agent's decision rule: π(a | s) gives the probability of taking action a in state s (or, for a deterministic policy, simply names one action per state). The captain's policy is the rule that maps every match situation to a batting approach.
Given a policy, the state-value function V^π(s) is the expected total discounted reward from starting in state s and following π forever after:
V^π(s) = E_π [ r_{t+1} + γ r_{t+2} + γ² r_{t+3} + ... | s_t = s ]
The discount γ is what keeps this sum finite when the process runs indefinitely, and it also encodes a preference: a reward k steps away is worth only γ^k of its face value today. The related action-value function Q^π(s, a) gives the expected discounted return of taking action a in state s right now, then following π afterward.
These two quantities are linked by a recursive identity, the Bellman equation, which is the single most important equation in this entire subject:
V^π(s) = Σ_a π(a|s) [ R(s,a) + γ Σ_s' P(s'|s,a) V^π(s') ]
Read it right to left: the value of a state equals the immediate reward, plus the discounted value of whatever state comes next, averaged over the action the policy takes and the randomness of the transition. This recursion exists only because of the Markov property: V^π(s') on the right-hand side does not need to know how the process reached s', because the state alone is a sufficient summary. Take the recursion and replace "follow policy π" with "take whichever action maximizes the right-hand side," and you get the Bellman optimality equation:
V*(s) = max_a [ R(s,a) + γ Σ_s' P(s'|s,a) V*(s') ]
V* is the value function of the best possible policy, π*. Value iteration is the algorithm that computes V* by turning this equation into an update rule and repeating it until the values stop changing: start with any guess V_0, and at each sweep compute V_{k+1}(s) = max_a [ R(s,a) + γ Σ_s' P(s'|s,a) V_k(s') ] for every state.
Worked example: value iteration on a two-state chase model
To make this fully concrete, collapse the run chase into a small MDP with two non-terminal states: M ("ahead of the required rate," momentum with the batting side) and P ("behind the required rate," under pressure). Actions in both states are Attack and Consolidate. For a clean, fully hand-computable example, treat this as a continuing (infinite-horizon) process with γ = 0.9, rather than an episodic one that terminates at the end of the innings; a real chase does end, which changes the boundary condition at the last over, but not the core recursion being demonstrated here. Define the dynamics as follows.
From M: Attack gives reward R(M,Attack) = 3 and transitions to M with probability 0.7, to P with probability 0.3. Consolidate gives reward R(M,Consolidate) = 1 and transitions to M with probability 0.9, to P with probability 0.1.
From P: Attack gives reward R(P,Attack) = 2 and transitions to M with probability 0.4, to P with probability 0.6. Consolidate gives reward R(P,Consolidate) = -1 and transitions to M with probability 0.2, to P with probability 0.8. (Attacking under pressure is riskier per ball but keeps the required rate honest; consolidating under pressure lets the rate creep away, hence the negative reward.)
Initialize V_0(M) = V_0(P) = 0 and apply the Bellman optimality update by hand.
Sweep 1. Q_1(M,Attack) = 3 + 0.9(0.7·0 + 0.3·0) = 3. Q_1(M,Consolidate) = 1 + 0.9(0.9·0 + 0.1·0) = 1. So V_1(M) = max(3, 1) = 3, achieved by Attack. Q_1(P,Attack) = 2 + 0.9(0.4·0 + 0.6·0) = 2. Q_1(P,Consolidate) = -1 + 0.9(0.2·0 + 0.8·0) = -1. So V_1(P) = max(2, -1) = 2, achieved by Attack.
Sweep 2. Q_2(M,Attack) = 3 + 0.9(0.7·3 + 0.3·2) = 3 + 0.9(2.1 + 0.6) = 3 + 0.9(2.7) = 3 + 2.43 = 5.43. Q_2(M,Consolidate) = 1 + 0.9(0.9·3 + 0.1·2) = 1 + 0.9(2.7 + 0.2) = 1 + 2.61 = 3.61. So V_2(M) = 5.43. Q_2(P,Attack) = 2 + 0.9(0.4·3 + 0.6·2) = 2 + 0.9(1.2 + 1.2) = 2 + 2.16 = 4.16. Q_2(P,Consolidate) = -1 + 0.9(0.2·3 + 0.8·2) = -1 + 0.9(0.6 + 1.6) = -1 + 1.98 = 0.98. So V_2(P) = 4.16.
Sweep 3. Q_3(M,Attack) = 3 + 0.9(0.7·5.43 + 0.3·4.16) = 3 + 0.9(3.801 + 1.248) = 3 + 0.9(5.049) = 3 + 4.5441 = 7.5441. Q_3(M,Consolidate) = 1 + 0.9(0.9·5.43 + 0.1·4.16) = 1 + 0.9(4.887 + 0.416) = 1 + 4.7727 = 5.7727. So V_3(M) = 7.5441. Q_3(P,Attack) = 2 + 0.9(0.4·5.43 + 0.6·4.16) = 2 + 0.9(2.172 + 2.496) = 2 + 4.2012 = 6.2012. Q_3(P,Consolidate) = -1 + 0.9(0.2·5.43 + 0.8·4.16) = -1 + 0.9(1.086 + 3.328) = -1 + 3.9726 = 2.9726. So V_3(P) = 6.2012.
In every sweep, Attack strictly beats Consolidate in both states, so the greedy policy has already settled by sweep 1: π*(M) = Attack, π*(P) = Attack. That means the exact fixed point can be found without further sweeping, by solving the two linear equations that Attack must satisfy at convergence:
V*(M) = 3 + 0.9(0.7·V*(M) + 0.3·V*(P)) and V*(P) = 2 + 0.9(0.4·V*(M) + 0.6·V*(P))
Simplifying: 0.37·V*(M) = 3 + 0.27·V*(P) and 0.46·V*(P) = 2 + 0.36·V*(M). Substituting the second into the first gives V*(M) = 1.92 / 0.073 ≈ 26.30, and back-substituting gives V*(P) ≈ 24.93. As a sanity check by an independent method (order-of-magnitude bound): rewards under Attack are roughly 2 to 3 per step, and the effective horizon of a discount of 0.9 is 1/(1-0.9) = 10 steps, so the value should land somewhere near 2.5 × 10 = 25. Both computed values, 26.30 and 24.93, land squarely in that band, confirming the arithmetic.
Here is the same recursion as code, traced against the hand computation above. Rounding to four decimals reproduces the sweep values exactly, since every intermediate number above terminates within four decimal places.
states = ['M', 'P']
actions = ['Attack', 'Consolidate']
transitions = {
'M': {'Attack': {'M': 0.7, 'P': 0.3}, 'Consolidate': {'M': 0.9, 'P': 0.1}},
'P': {'Attack': {'M': 0.4, 'P': 0.6}, 'Consolidate': {'M': 0.2, 'P': 0.8}},
}
rewards = {
'M': {'Attack': 3, 'Consolidate': 1},
'P': {'Attack': 2, 'Consolidate': -1},
}
gamma = 0.9
V = {'M': 0.0, 'P': 0.0}
for sweep in range(3):
new_V = {}
for s in states:
q_values = []
for a in actions:
expected_next = sum(p * V[s_next] for s_next, p in transitions[s][a].items())
q_values.append(rewards[s][a] + gamma * expected_next)
new_V[s] = max(q_values)
V = new_V
print(sweep + 1, {k: round(v, 4) for k, v in V.items()})
# Output:
# 1 {'M': 3.0, 'P': 2.0}
# 2 {'M': 5.43, 'P': 4.16}
# 3 {'M': 7.5441, 'P': 6.2012}The state-transition structure driving this computation, under the optimal Attack action, is shown in the diagram below alongside the general agent-environment loop it is one instance of.
Beyond the boundary rope
The same tuple that models the run chase models a much wider class of problems that platforms operating in India actually solve using exactly this machinery: a delivery platform batching which order a rider should pick up next given its current location and pending orders, a ride-hailing system deciding when to activate surge pricing in a zone given current demand and supply, a UPI fraud-interdiction system deciding whether to hold or clear a transaction given the account's recent pattern. Every one of these fits the same skeleton: a current state that is engineered to be Markov-sufficient, a set of actions, transition probabilities driven by real-world uncertainty, and a reward reflecting the objective the system is built to optimize. Q-learning and policy gradients, covered in later chapters, are algorithms for learning near-optimal policies when P and R are not known in advance and must instead be estimated from experience. Value iteration, worked by hand above, is what those algorithms are approximating once the model is known.
Active recall
Attempt each question before reading its answer.
Q1. Write out the five components of the MDP tuple (S, A, P, R, γ) for the two-state run-chase model used in the worked example.
Q2. Why must the reward be written R(s, a), a function of both state and action, rather than R(s), a function of state alone?
Q3. Using V_1(M) = 3 and V_1(P) = 2 from sweep 1, compute Q_2(P, Attack) by hand and confirm it matches the value obtained in sweep 2 of the worked example.
Q4. A classmate says: "An MDP assumes the world has no memory of the past, which is unrealistic for something like cricket momentum." Explain what is wrong with this statement and how it should be corrected.
Q5. If the discount factor were γ = 0 instead of 0.9, what would V*(M) and V*(P) equal, and why does this follow directly from the Bellman optimality equation?
Q6. Under what precise condition does conditioning a decision on the full over-by-over history become no more useful than conditioning on the current state alone?
A1. S = {M, P} (ahead of / behind the required rate). A = {Attack, Consolidate}. P(s'|s,a) is the table of four transition distributions given in the setup (e.g. P(M|M,Attack) = 0.7). R(s,a) is the reward table (e.g. R(M,Attack) = 3). γ = 0.9.
A2. The same state can lead to very different immediate payoffs depending on what the agent chooses to do there. State M under Attack yields reward 3; state M under Consolidate yields reward 1. If reward depended only on s, the model could never express that the choice of action itself has consequences, which would make the "decision" part of "decision process" meaningless: every action from a given state would be rewarded identically, so there would be nothing to optimize.
A3. Q_2(P,Attack) = R(P,Attack) + γ(0.4·V_1(M) + 0.6·V_1(P)) = 2 + 0.9(0.4·3 + 0.6·2) = 2 + 0.9(1.2 + 1.2) = 2 + 0.9(2.4) = 2 + 2.16 = 4.16, which matches V_2(P) = 4.16 exactly, since Attack is the maximizing action in sweep 2.
A4. The Markov property is not a claim that the past has no causal effect on the future; momentum in cricket is real. It is a statement about what the state variable must capture: the current state must be a sufficient summary of everything decision-relevant about the history. If momentum genuinely matters, the fix is to build it into the state (for example, adding "runs scored in the last two overs" as a state component), not to abandon the framework. Any history-dependent process can be made Markov by enriching the state; the property is a target for state design, not a restriction on which real processes can be modeled.
A5. With γ = 0, the Bellman optimality equation collapses to V*(s) = max_a R(s,a), since the entire second term is multiplied by zero and vanishes regardless of the transition probabilities or future values. This means V*(M) = max(3, 1) = 3 and V*(P) = max(2, -1) = 2, which are exactly the sweep-1 values computed earlier. The discount factor of zero makes the agent perfectly myopic: it always picks the action with the best immediate reward and never looks past the current step, so value iteration converges in a single sweep.
A6. Precisely when the current state has already been engineered to be a sufficient statistic for the full history, that is, when P(s_{t+1} | s_t, a_t, s_{t-1}, a_{t-1}, ..., s_0, a_0) = P(s_{t+1} | s_t, a_t) holds exactly. In that case the earlier history carries no additional information about what happens next beyond what the current state already encodes, so conditioning on more of it cannot improve a transition or reward prediction, by the definition of the Markov property itself.
Think About It
Think about this: How would you explain markov decision processes: foundations of sequential decision making to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.
Practice Exercises
Now it is time to practice! Complete these challenges to solidify your understanding:
- Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
- Exercise 2: Find a real-world example where markov decision processes: foundations of sequential decision making is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
- Exercise 3: Create a mind-map connecting markov decision processes: foundations of sequential decision making to at least 3 other topics you have studied.