Reinforcement Learning Fundamentals: MDPs, Policies and Value Functions

Reinforcement learning feels different from supervised learning the first time you build an agent that learns from interaction rather than labeled examples. There is no dataset of correct actions handed to you. Instead, you have an environment that responds to what your agent does, and a scalar reward signal that tells you whether the outcome was good or bad. When I built my first RL system for a simulated inventory control problem, I wasted weeks trying to frame it as a classification task before I understood that I needed a formal way to describe sequential decision-making under uncertainty. That formalism is the Markov Decision Process, and once you understand MDPs, policies, and value functions, the rest of reinforcement learning starts to make sense. This article lays out those fundamentals the way I wish someone had explained them to me early on — with enough mathematical precision to be useful, but grounded in implementation details you will actually use.

Framing Sequential Decisions as Markov Decision Processes

In my experience, the most common mistake beginners make is jumping straight to algorithms like Q-learning without understanding the problem structure those algorithms are designed to solve. Every reinforcement learning problem can be described as a Markov Decision Process. An MDP gives you a language to define what the agent sees, what it can do, and how the environment responds. If your problem cannot be cast as an MDP, you probably have not defined your state or reward correctly.

An MDP is defined by a tuple (S, A, P, R, γ). S is the set of states, A is the set of actions, P is the transition dynamics, R is the reward function, and γ is the discount factor. The interaction proceeds in discrete timesteps. At time t, the environment is in state s_t. The agent selects an action a_t, the environment transitions to a new state s_{t+1} according to P, and the agent receives a reward r_{t+1}. This loop continues until termination or indefinitely. The goal is to find a way of acting that maximizes cumulative reward.

The Markov Property and Why State Definition Matters

The Markov property is the central assumption: the future depends only on the present state, not on the full history. Formally, P(s_{t+1} | s_t, a_t, s_{t-1}, a_{t-1}, ...) = P(s_{t+1} | s_t, a_t). In practice, this rarely holds perfectly, and I've found that designing the state representation is where most real projects succeed or fail. If your state omits critical history, your agent cannot learn an optimal strategy no matter how much training you do.

For example, in a robotics navigation task, if your state contains only the current LiDAR reading but not velocity, the agent cannot predict where it will be next. The environment will appear non-Markovian, training will be unstable, and value estimates will be noisy. The fix is to augment the state until it is sufficiently informative — by stacking recent observations, adding velocity estimates, or using recurrent encoders. When you are Designing Custom Gymnasium Environments for RL Training, spending time on state design pays off more than tuning hyperparameters later.

Discrete and Continuous Spaces in Practice

In a gridworld, S and A are small and discrete, which makes it easy to reason about tables of values. In real problems, states are often high-dimensional continuous vectors (joint angles, images, market indicators) and actions may be continuous torques or discretized choices. The MDP formalism handles both, but your choice of function approximation will change completely. Tabular methods work for the former; neural networks become necessary for the latter. This distinction determines whether you can enumerate states or must generalize from experience.

# Minimal MDP interface in Python - the core loop every RL environment implements
import numpy as np

class SimpleGridMDP:
    def __init__(self, size=4, gamma=0.99):
        self.size = size
        self.gamma = gamma
        self.state = 0  # start state index
        # 0: up, 1: right, 2: down, 3: left
        self.n_states = size * size
        self.n_actions = 4
    
    def step(self, action):
        # Transition dynamics P(s'|s,a) - here deterministic for clarity
        x, y = self.state % self.size, self.state // self.size
        if action == 0 and y > 0: y -= 1
        elif action == 1 and x < self.size - 1: x += 1
        elif action == 2 and y < self.size - 1: y += 1
        elif action == 3 and x > 0: x -= 1
        
        self.state = y * self.size + x
        # Reward function R(s,a,s')
        reward = 10.0 if self.state == self.n_states - 1 else -0.1
        done = self.state == self.n_states - 1
        return self.state, reward, done
    
    def reset(self):
        self.state = 0
        return self.state

This loop — reset, step, reward, done — is exactly what Gymnasium implements, and understanding it as an MDP sampler makes debugging far easier. When an agent fails to learn, I first check whether my step() function correctly implements the transition and reward I intended.

Decoding Transition Dynamics and Reward Signals in MDPs

Once you have states and actions, the two functions that define your MDP's behavior are P and R. They describe the rules of the world, and your agent must learn to act well without necessarily knowing them explicitly.

The transition function P(s'|s,a) gives the probability of landing in state s' after taking action a in state s. In a model-based view, you would learn or be given P directly and could plan ahead. In model-free RL, which is far more common when you start out, you never estimate P explicitly; you just sample from it by interacting with the environment. I've found that being clear about this distinction early prevents a lot of confusion when reading papers that talk about model-based methods.

The reward function R(s,a,s') is arguably more important than the dynamics. It encodes the objective. A poorly shaped reward makes even a perfect algorithm learn the wrong behavior. Rewards can be sparse (only at goal achievement, like +1 for winning a game) or dense (small rewards at each step, like negative distance to target). Sparse rewards are easier to specify correctly but much harder to learn from, because the agent receives almost no feedback. Dense rewards speed up learning but can introduce unintended incentives if you are not careful.

Discount Factor as a Horizon Control

The discount factor γ in [0,1) balances immediate versus future rewards. The return G_t is defined as G_t = r_{t+1} + γ r_{t+2} + γ^2 r_{t+3} + ... . With γ close to 0, the agent is myopic and cares only about immediate reward. With γ close to 1, it values long-term return and will tolerate short-term penalties for larger eventual payoffs. In episodic tasks with sparse final rewards, you typically want γ = 0.99 or higher. In my early experiments with a cart-pole controller, lowering γ from 0.99 to 0.9 made the agent greedily keep the pole balanced for a few steps but fail to learn stable long-term control.

Discounting also has a mathematical purpose: it ensures the infinite-horizon sum remains finite and makes value iteration converge. For continuing tasks without natural termination, discounting is not optional.

Exposure to Episodic vs Continuing Tasks

Episodic tasks have a terminal state (a game ends, a robot reaches a target), after which the return is computed and the environment resets. Continuing tasks run indefinitely, and you optimize average or discounted reward over an infinite horizon. Most benchmarks you will use as a beginner — GridWorld, MountainCar, CartPole — are episodic, which simplifies evaluation. Just remember that your reward design and value estimation need to account for termination correctly; bootstrapping from a terminal state should yield zero future value.

From Deterministic Maps to Stochastic Behaviors: Understanding Policies

A policy defines how the agent behaves. Formally, a policy π is a mapping from states to actions. A deterministic policy π(s) = a selects one action per state. A stochastic policy π(a|s) gives a probability distribution over actions conditioned on the state. Both are valid, and the choice has significant practical consequences.

Deterministic policies are easier to interpret: in a given situation, do this one thing. They are sufficient for many environments where an optimal deterministic policy exists, which is true for any finite MDP. Stochastic policies, however, are essential when exploration is required, when the environment is partially observable, or when you are optimizing against an adversary. They also form the basis for modern policy gradient methods, where you differentiate through the policy distribution.

Why Stochastic Policies Dominate Early Training

If you always act deterministically, you may never try actions that would turn out to be better. A stochastic policy naturally explores. At the start of training, you want high entropy — actions sampled broadly. As training progresses, the distribution sharpens around high-value actions. I've found that controlling this entropy is one of the most sensitive parts of policy optimization. Too little entropy and the agent converges prematurely to a poor strategy; too much and it never exploits what it has learned.

In policy gradient implementations built with PyTorch Documentation, a stochastic policy is typically represented as a neural network that outputs parameters of a distribution — logits for a categorical distribution over discrete actions, or mean and variance for a Gaussian over continuous actions. Sampling from that distribution gives you the action to execute.

import torch
import torch.nn as nn
import torch.nn.functional as F

class StochasticPolicy(nn.Module):
    def __init__(self, state_dim, action_dim):
        super().__init__()
        self.net = nn.Sequential(
            nn.Linear(state_dim, 128),
            nn.ReLU(),
            nn.Linear(128, 128),
            nn.ReLU(),
            nn.Linear(128, action_dim)  # logits for discrete actions
        )
    
    def forward(self, state):
        logits = self.net(state)
        return torch.distributions.Categorical(logits=logits)
    
    def act(self, state):
        # state: tensor of shape [state_dim]
        dist = self.forward(state)
        action = dist.sample()
        log_prob = dist.log_prob(action)
        entropy = dist.entropy()
        return action.item(), log_prob, entropy

# Usage during rollout
# policy = StochasticPolicy(state_dim=4, action_dim=2)
# action, log_prob, entropy = policy.act(torch.randn(4))

Deterministic Policies for Deployment Efficiency

After training a stochastic policy, you often deploy the deterministic mean action (for Gaussians) or argmax (for categorical) to reduce variance at test time. In off-policy algorithms like DDPG or TD3 for continuous control, the policy is explicitly deterministic and exploration is added via external noise processes like Ornstein-Uhlenbeck or Gaussian perturbations. Understanding when to use each form will help you when you later compare Deep RL Algorithms: DQN, PPO and SAC Compared, as PPO is inherently stochastic while DDPG is deterministic.

Value Functions as the Compass for Long-Term Decision Quality

Rewards tell you how good an immediate transition was. Value functions tell you how good a state or state-action pair is in the long run. They are expectations of cumulative discounted return under a particular way of behaving, and they are the central learning target in most RL algorithms.

There are two core value functions. The state-value function V^π(s) = E_π[G_t | s_t = s] is the expected return starting from state s and following policy π thereafter. The action-value function Q^π(s,a) = E_π[G_t | s_t = s, a_t = a] is the expected return starting from state s, taking action a, then following π. Intuitively, V tells you how good it is to be in a situation, while Q tells you how good it is to take a specific action in that situation.

In my experience, the relationship Q(s,a) = R(s,a) + γ * sum_{s'} P(s'|s,a) V(s') becomes much clearer when you implement it rather than just read it. Q incorporates the immediate reward plus the discounted value of where you land. The advantage function A^π(s,a) = Q^π(s,a) - V^π(s) then tells you how much better action a is than the average behavior of π in state s. This last quantity is surprisingly important for reducing variance in policy gradients, as seen in modern alignment work like RLHF for Language Models: Reward Modeling and Policy Optimization.

How Value Functions Guide Policy Improvement

Value functions are not the goal themselves; they are a critic that guides the actor (the policy) toward improvement. If you can accurately estimate Q^π, you can improve π by making it more likely to select actions with higher Q-values. This alternating cycle — estimate values for the current policy, then improve the policy to be greedy with respect to those values — is called Generalized Policy Iteration and underlies almost all RL methods.

When values are stored in tables, each state has an exact entry. With function approximation, a neural network V_θ(s) or Q_θ(s,a) must generalize across similar states, which introduces approximation error and the risk of overestimation bias. I have seen many beginners underestimate this shift; moving from a 16-state gridworld where tabular valuation is exact to a 100-dimensional continuous state where a network must extrapolate is a qualitative change in difficulty.

The Bellman Recursion: How Value Functions Bootstrap Themselves

Bellman equations are the self-consistency conditions that all true value functions must satisfy. They express the value of a state in terms of the values of successor states, which allows RL to learn from incomplete episodes by bootstrapping — updating an estimate based on another estimate.

For a fixed policy π, the Bellman expectation equation for V is: V^π(s) = sum_a π(a|s) sum_{s',r} P(s',r|s,a) [r + γ V^π(s')]. In words: the value of s is the average over actions π would take, and over possible next states and rewards, of immediate reward plus discounted value of the next state. The corresponding equation for Q is: Q^π(s,a) = sum_{s',r} P(s',r|s,a) [r + γ sum_{a'} π(a'|s') Q^π(s',a')].

Optimality versions replace the average over π with a max. The optimal state-value V*(s) = max_a sum_{s',r} P(s',r|s,a) [r + γ V*(s')], and Q*(s,a) = sum_{s',r} P(s',r|s,a) [r + γ max_{a'} Q*(s',a')]. These equations characterize the value functions of the best possible policy. If you can solve them, the optimal policy is simply greedy with respect to Q*.

Bootstrapping Versus Monte Carlo Estimation

There are two broad ways to estimate values from experience. Monte Carlo methods wait until the end of an episode, compute the actual observed return G_t, and update V(s_t) toward G_t. This is unbiased but high variance and cannot be used until episodes terminate. Temporal-difference (TD) methods bootstrap: they update V(s_t) toward r_{t+1} + γ V(s_{t+1}), using the current estimate of the next state's value. TD has lower variance and learns online after each step, but introduces bias early in training when estimates are poor.

Most practical algorithms blend the two. TD(λ) and Generalized Advantage Estimation mix multi-step returns to trade off bias and variance. When I tune this for a new environment, I treat λ or the number of n-step returns as a first-class hyperparameter, not an afterthought, because it directly affects stability. You can find thorough recent discussions of these tradeoffs in papers on arXiv Machine Learning that compare estimation methods across benchmark suites.

Value Iteration as a Direct Bellman Solver

In small tabular MDPs where P and R are known, you can apply the Bellman optimality equation as an iterative update: V_{k+1}(s) = max_a sum_{s',r} P(s',r|s,a)[r + γ V_k(s')]. This is value iteration, and it converges to V* regardless of initialization. Implementing it once, even for a toy problem, makes the abstract recursion concrete.

import numpy as np

def value_iteration(P, R, gamma=0.99, theta=1e-6):
    """
    P: transition matrix shape [n_states, n_actions, n_states]
    R: reward matrix shape [n_states, n_actions]
    Returns optimal V and deterministic policy
    """
    n_states, n_actions = R.shape
    V = np.zeros(n_states)
    
    while True:
        delta = 0
        for s in range(n_states):
            v = V[s]
            # Bellman optimality update
            q_values = np.zeros(n_actions)
            for a in range(n_actions):
                q_values[a] = R[s, a] + gamma * np.sum(P[s, a] * V)
            V[s] = np.max(q_values)
            delta = max(delta, abs(v - V[s]))
        if delta < theta:
            break
    
    # Extract greedy policy from optimal values
    policy = np.zeros(n_states, dtype=int)
    for s in range(n_states):
        q_values = np.array([R[s, a] + gamma * np.sum(P[s, a] * V) for a in range(n_actions)])
        policy[s] = np.argmax(q_values)
    
    return V, policy

# For a 4x4 gridworld with 16 states, this converges in <100 iterations.
# For large or continuous spaces, this tabular approach is intractable and
# we replace it with sampled TD updates and function approximation.

Value iteration shows why the Bellman equation matters: it is not just an identity, it is an algorithm. Modern deep RL algorithms are essentially sampled, approximate versions of this same idea scaled to environments where you cannot enumerate states.

Linking Value Estimation to Policy Improvement in Practice

Knowing definitions is not enough; you need to see how policies and value functions interact during learning. The pattern is consistent across methods, even when implementation details differ dramatically.

You start with an initial policy, often random. You collect trajectories by running that policy in the environment. You use those trajectories to estimate V or Q, either by Monte Carlo regression or by TD bootstrapping. You then improve the policy to favor actions that your value estimates suggest are better. Repeat. This loop is what connects the three concepts together: the MDP defines the data-generating process, the policy generates behavior, and the value function evaluates that behavior to drive improvement.

In practice, this loop is noisy and sensitive. Value estimates bootstrap from themselves, so early errors propagate. Policies change the data distribution, making previously accurate values obsolete. I've found that three practical habits help stabilize this cycle. First, use a separate target network or slowly updated critic when bootstrapping, so the regression target does not move every gradient step. Second, normalize advantages or rewards so that value loss magnitudes remain in a reasonable range across environments. Third, monitor not just episode return but also value loss, policy entropy, and advantage variance during training — they reveal failures earlier than return curves alone.

Choosing a Starting Algorithm After the Fundamentals

Once you are comfortable with MDPs, policies, and values, you have a clear path to first algorithms. For discrete actions and tabular or moderately sized state spaces, start with Q-learning or SARSA to see bootstrapped action-value learning in its purest form. For policy-based learning with neural networks, REINFORCE with a learned baseline introduces the policy gradient theorem directly, and PPO builds on it with clipping to limit destructive updates. Value-based methods like DQN show how to combine Q-learning with deep function approximation and experience replay. Each of these is a different way of solving the same underlying Bellman relationships under sampling and approximation constraints.

Before scaling up to image observations or continuous control, I recommend reimplementing tabular value iteration and Monte Carlo policy evaluation from scratch on a custom 5x5 gridworld where you control the transition noise. Measure how γ, exploration rate, and reward sparsity affect convergence speed and final policy quality. That small experiment will teach you more about the interaction of MDP structure, policy stochasticity, and value accuracy than running a large benchmark suite blindly.

Frequently Asked Questions