Reinforcement Learning and Markov Decision Processes

How does a program learn to play chess, balance a robot or manage a warehouse without anyone labelling the right answer for each situation? Reinforcement learning (RL) gives an agent rewards and penalties and lets it discover good behaviour through trial and error. The mathematical framework underneath is the Markov decision process, and with a couple of equations you can solve small RL problems entirely by hand.

The Agent–Environment Loop

At each time step \( t \):

1. The agent observes the current state \( s_t \).
2. It chooses an action \( a_t \).
3. The environment returns a reward \( r_{t+1} \) and a new state \( s_{t+1} \).

The agent's goal is not to grab the biggest immediate reward but to maximise the total reward over time. A chess move that sacrifices a piece may lose material now but win the game later.

Markov Decision Processes

A Markov decision process (MDP) is described by five ingredients:

• A set of states \( S \).
• A set of actions \( A \).
• Transition probabilities \( P(s' \mid s, a) \): the chance of moving to \( s' \) after taking action \( a \) in state \( s \).
• A reward function \( R(s, a) \): the expected immediate reward.
• A discount factor \( \gamma \in [0, 1) \).

The word "Markov" refers to the Markov property: the future depends only on the current state and action, not on the full history. Formally, \( P(s_{t+1} \mid s_t, a_t, s_{t-1}, \dots) = P(s_{t+1} \mid s_t, a_t) \). A good state description contains everything relevant from the past.

Returns and Discounting

The return from time \( t \) is the discounted sum of future rewards:

$$ G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1}. $$

Discounting does two jobs. It expresses a preference for sooner rewards (like interest on money), and it keeps the infinite sum finite: if every reward is at most \( R_{\max} \), then \( G_t \le R_{\max}/(1 - \gamma) \).

For example, with rewards \( 1, 0, 2, 5 \) followed by nothing, and \( \gamma = 0.9 \):

$$ G_0 = 1 + 0.9(0) + 0.9^2(2) + 0.9^3(5) = 1 + 0 + 1.62 + 3.645 = 6.265 . $$

Policies and Value Functions

A policy \( \pi(a \mid s) \) tells the agent what to do in each state. To judge a policy we use two value functions:

• The state value \( V^\pi(s) = \mathbb{E}_\pi[G_t \mid s_t = s] \): the expected return starting in \( s \) and following \( \pi \).
• The action value \( Q^\pi(s, a) = \mathbb{E}_\pi[G_t \mid s_t = s, a_t = a] \): the expected return after taking \( a \) in \( s \) and following \( \pi \) afterwards.

The Bellman Equations

Richard Bellman's key insight in the 1950s was that a return splits into the immediate reward plus the discounted return from the next state. This gives the Bellman expectation equation:

$$ V^\pi(s) = \sum_{a} \pi(a \mid s) \left[ R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V^\pi(s') \right]. $$

For the best possible policy, the agent takes the action that maximises this quantity, giving the Bellman optimality equation:

$$ V^*(s) = \max_{a} \left[ R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V^*(s') \right]. $$

For a fixed policy, the Bellman equations are a system of linear equations; for the optimal policy, the max makes them non-linear, but they can be solved iteratively.

A Small Example MDP

Consider a student who can be in one of two states, A (fresh) or B (tired). Use \( \gamma = 0.9 \).

• In A, the action work gives reward 2 and leads to B for certain.
• In A, the action revise lightly gives reward 1 and keeps the student in A.
• In B, the only action rest gives reward 0 and leads to A or stays in B, each with probability 0.5.

Worked Example 1: Evaluating the "Always Work" Policy

Under this policy the Bellman expectation equations are

$$ V(A) = 2 + 0.9\, V(B), \qquad V(B) = 0 + 0.9\left[0.5\, V(A) + 0.5\, V(B)\right]. $$

Step 1. Simplify the second equation. \( V(B) = 0.45 V(A) + 0.45 V(B) \), so \( 0.55 V(B) = 0.45 V(A) \) and \( V(B) = \tfrac{9}{11} V(A) \approx 0.8182\, V(A) \).

Step 2. Substitute into the first. \( V(A) = 2 + 0.9 \times \tfrac{9}{11} V(A) = 2 + \tfrac{81}{110} V(A) \).

Step 3. Solve. \( V(A)\left(1 - \tfrac{81}{110}\right) = 2 \Rightarrow V(A) \times \tfrac{29}{110} = 2 \Rightarrow V(A) = \tfrac{220}{29} \approx 7.586 \).

Step 4. Back-substitute. \( V(B) = \tfrac{9}{11} \times \tfrac{220}{29} = \tfrac{180}{29} \approx 6.207 \).

Step 5. Check. \( 2 + 0.9(6.207) = 7.586 \) and \( 0.9(0.5 \times 7.586 + 0.5 \times 6.207) = 0.9 \times 6.8965 \approx 6.207 \). Both equations hold.

Worked Example 2: Value Iteration for the Optimal Policy

Is "always work" the best the student can do? Value iteration applies the optimality equation repeatedly, starting from \( V_0 = 0 \).

Iteration 1.

• \( V_1(A) = \max(2 + 0.9 \times 0,\; 1 + 0.9 \times 0) = \max(2, 1) = 2 \)
• \( V_1(B) = 0.9(0.5 \times 0 + 0.5 \times 0) = 0 \)

Iteration 2.

• \( V_2(A) = \max(2 + 0.9 \times 0,\; 1 + 0.9 \times 2) = \max(2, 2.8) = 2.8 \)
• \( V_2(B) = 0.9(0.5 \times 2 + 0.5 \times 0) = 0.9 \)

Iteration 3.

• \( V_3(A) = \max(2 + 0.9 \times 0.9,\; 1 + 0.9 \times 2.8) = \max(2.81, 3.52) = 3.52 \)
• \( V_3(B) = 0.9(0.5 \times 2.8 + 0.5 \times 0.9) = 0.9 \times 1.85 = 1.665 \)

Light revision has already taken the lead. Continuing, the values converge to the solution of the optimality equations with "revise lightly" chosen in A:

$$ V^*(A) = \frac{1}{1 - 0.9} = 10, \qquad V^*(B) = 0.9(0.5 \times 10 + 0.5\, V^*(B)) \Rightarrow V^*(B) = \frac{4.5}{0.55} \approx 8.182 . $$

Sanity check. In A, working would give \( 2 + 0.9 \times 8.182 \approx 9.364 \), which is less than 10, so revising lightly is indeed optimal. Steady reward of 1 forever is worth more than a reward of 2 followed by a tiring spell earning nothing. The maths overturns the greedy choice.

Learning Without a Model: Q-Learning

Value iteration needs the transition probabilities. In most real problems the agent does not know them and must learn from experience. Q-learning, introduced by Chris Watkins in 1989, updates action values from single observed transitions \( (s, a, r, s') \):

$$ Q(s, a) \leftarrow Q(s, a) + \alpha \left[ r + \gamma \max_{a'} Q(s', a') - Q(s, a) \right]. $$

The bracket is the temporal-difference error: the gap between the new estimate \( r + \gamma \max Q(s', \cdot) \) and the old one. For instance, with \( Q(s, a) = 5 \), \( r = 2 \), \( \max_{a'} Q(s', a') = 10 \), \( \gamma = 0.9 \) and learning rate \( \alpha = 0.1 \):

$$ Q(s, a) \leftarrow 5 + 0.1\,[2 + 9 - 5] = 5 + 0.6 = 5.6 . $$

To learn well, the agent must balance exploration (trying new actions) and exploitation (using what it knows). A simple strategy, \( \varepsilon \)-greedy, picks a random action with probability \( \varepsilon \), such as 0.1, and the best-known action otherwise.

When states are too numerous for a table, as with raw game screens, a neural network approximates \( Q(s, a) \). This deep Q-network approach learned to play many Atari games from pixels, and related methods power game-playing systems and robotics research.

Did You Know?

• Bellman coined the term "dynamic programming" partly, he later said, because it sounded impressive and avoided words like "research" and "mathematical" that worried the officials overseeing his work.
• With \( \gamma = 0.9 \), a reward 10 steps away is worth only \( 0.9^{10} \approx 0.35 \) of the same reward today.
• Reinforcement learning from human feedback is used to fine-tune modern chatbots, treating human preference judgements as rewards.

Key Takeaways

• An MDP is defined by states, actions, transition probabilities, rewards and a discount factor.
• The return is a discounted sum of rewards, bounded by \( R_{\max}/(1 - \gamma) \).
• Bellman equations express a state's value as immediate reward plus discounted future value.
• Policy evaluation solves linear equations; value iteration repeatedly applies the optimality equation.
• Q-learning learns optimal action values from experience without knowing the transition model.

Need help solving an MDP, a Bellman equation or an RL assignment? Amathify's experts and PhD scholars provide step-by-step solutions via WhatsApp or the Ask a Question form.