Skip to main content

View as Markdown

Page content converted to Markdown. Use the original page link at the end to explore interactive graphics.

2. Markov Decision Processes

A Markov decision process (MDP) is the core problem model in reinforcement learning. Whether training a quadruped to walk or a robotic arm to grasp, the first step is to identify the state space, action space, transition probabilities, and reward function.

For unfamiliar symbols, consult the terms and formulas quick reference. Expand the plain-language explanations beside this chapter's formulas without leaving the page.

Embodied AI perspective: For robotic grasping, the state might contain joint angles and object poses, the action might specify joint torques, and the reward might indicate grasp success. Defining these elements makes the task suitable for RL.

2.1 Agent–environment interaction​

An agent interacts with its environment over discrete time steps. At step , it observes state and selects action . After executing that action, it receives reward and the environment moves to state .

Reward time-index convention

Chapters 2–6 (MDPs, dynamic programming, Monte Carlo, temporal difference, and DQN) index rewards by the step at which they arrive: executing produces and leads to . is the immediate reward for the current action ; no reward is skipped.

Uppercase denote random variables; lowercase denote observed samples. Changing case does not shift the time index. In the interaction diagram below, the reward already available to the agent at step came from the previous action ; the environment responds to the current action with .

The later policy-gradient, Actor-Critic, and SAC chapters retain the convention of indexing rewards by the action that produces them. The sample correspondence is , so denotes the same return. In PPO, is a policy probability ratio, not a reward.

The agent sends action a_t; the environment returns reward r_t+1 and state s_t+1.

Agent–environment interaction (labels in Chinese)

Repeating this interaction produces a trajectory:

A complete trajectory from an initial state to a terminal state is an episode, ending after a finite number of steps .

To solve a problem with RL, first specify its state space, action space, transition probabilities, and reward function. An MDP is commonly defined as the tuple:

Here is the state space, the action space, the transition probability matrix, the reward function, and the discount factor between and .

2.2 The Markov property​

The central assumption is the Markov property: the distribution of the next state depends only on the current state and action, not on the earlier history:

In plain language: why does the Markov property only need the present?

The point is that the current state contains enough information, not that the robot must forget the past. A ball's position alone usually cannot tell you where it will move next; including velocity gives you more information. The vertical bar means “given this information.” The equality says that adding the past history does not change the conditional distribution of the next state.

More context: states versus observations.

Real robots typically receive partial observations. For example, a current lidar scan may miss occluded objects. Such problems can be modeled as partially observable Markov decision processes (POMDPs). Stacking past frames can help approximate a Markov state, but does not guarantee recovery of the full state.

2.3 State transition matrices​

For a finite state space, a directed graph can show how states connect:

State transitions in a Markov chain

A Markov chain

Transition probabilities can be represented as a matrix:

Here is the number of states. The probabilities of transitioning from one state to all possible next states sum to . The transition matrix is part of the environment model.

2.4 Objectives and returns​

The agent aims to learn a policy whose actions maximize expected cumulative reward. This cumulative quantity is called the return:

The discount factor controls how much future rewards matter. Values near emphasize immediate rewards; values near place more weight on the future.

For an episode terminating at , the sum stops at and . For example, suppose action from yields , then action yields and terminates the episode. With , the sampled returns are and . The reward for the current action is the first term of .

A useful measure of the discount factor's reach is the effective horizon:

For , gives a rough timescale of steps; rewards after step are not discarded. The expression comes from summing the geometric series of discount weights for . Robot walking tasks often use a large discount factor to account for sustained stability.

The return has the recursive definition:

Step by step: how does a long reward sum become two terms?
  1. Keep the first term , the reward just produced by the current action.
  2. Every remaining term contains at least one factor of . Factor it out.
  3. What remains in parentheses is exactly the return starting at the next time step, :

This is just factoring: no future rewards disappear. Check with the two-step example above: and .

Symbol guide: , powers, and time indices.

2.5 Policies and values​

2.5.1 Policy​

A policy specifies how actions are chosen in a state:

Policies may be deterministic, always choosing the same action in a given state, or stochastic, sampling actions from a distribution. Stochastic policies are common in embodied AI because they support exploration and robustness.

2.5.2 State value​

The state-value function is the expected return from a state when following policy :

In plain language: how do I read the expectation and conditional bar?

Read the formula as: “Starting at state and then following policy , what is the average return?” means a probability-weighted average; specifies the starting state. Even from the same state, action sampling or environmental randomness can produce different outcomes. Value is not the actual return of one trajectory.

For example, returns of and , each with probability one half, have expectation . A single run need not return .

Quick reference: expectation and value.

2.5.3 Action value​

The action-value function is the expected return given state and action :

2.5.4 Relating state and action values​

In plain language: why is V a weighted average of Q?

fixes the first action and follows afterward. lets choose even that first action. Multiply each action's score by the probability that the policy chooses it, then add the results.

If the left and right actions have values and , and each is selected with probability , then . Taking the maximum, , would instead correspond to a different policy that always selects the higher-scoring first action.

State value is the policy-weighted average of action values. It evaluates following the policy from a state, while action value evaluates choosing a particular action there.

2.6 Model-based and model-free methods​

  • Model-based methods use transition probabilities and reward functions for planning or decision-making, as in dynamic programming. Simulation sometimes makes such models available to accelerate learning.
  • Model-free methods learn directly from interaction without requiring an environment model, as in PPO and SAC. They are widely used with real robots whose dynamics are difficult to model precisely.

2.7 Prediction and control​

  • Prediction evaluates a given policy by estimating its value function.
  • Control searches for a policy that maximizes cumulative return.

Complex problems often require both: estimating values while improving the policy. This is the idea behind the Actor-Critic framework.