Core Concepts of Reinforcement Learning

Understanding Markov Decision Processes, value functions, policies, and the Bellman equations that form the mathematical foundation of RL.

Markov Decision Process (MDP)

An MDP is the formal mathematical framework for RL problems. It is defined by a tuple (S, A, P, R, γ):

• S - Set of states (all possible situations the agent can be in)
• A - Set of actions (all possible moves the agent can make)
• P(s'|s, a) - Transition probability (probability of reaching state s' from state s after action a)
• R(s, a, s') - Reward function (immediate reward for transitioning from s to s' via action a)
• γ - Discount factor (0 ≤ γ ≤ 1), determines how much the agent values future rewards vs immediate ones

Returns and Discount Factor

The agent's goal is to maximize the expected cumulative discounted reward (return):

G_t = r_{t+1} + γ * r_{t+2} + γ² * r_{t+3} + ... = ∑ γ^k * r_{t+k+1}

Value Functions

Value functions estimate how good it is to be in a given state (or to take an action in a given state):

• State-Value Function Vπ(s): Expected return starting from state s, following policy π. "How good is it to be in this state?"
• Action-Value Function Qπ(s, a): Expected return starting from state s, taking action a, then following policy π. "How good is it to take this action in this state?"

import numpy as np

# Simple grid world: 4x4 grid, goal at (3,3)
num_states = 16
gamma = 0.9

# Initialize value function
V = np.zeros(num_states)

# Iterative policy evaluation
for iteration in range(100):
    V_new = np.zeros(num_states)
    for s in range(num_states):
        if s == 15:  # Terminal state (goal)
            V_new[s] = 0
            continue
        # Average over all actions (random policy)
        for action in ['up', 'down', 'left', 'right']:
            next_s = get_next_state(s, action)
            reward = -1  # -1 per step to encourage shortest path
            V_new[s] += 0.25 * (reward + gamma * V[next_s])
    V = V_new

print("Value function:")
print(V.reshape(4, 4).round(1))

Bellman Equations

The Bellman equations express the relationship between the value of a state and the values of its successor states. They are the foundation of nearly every RL algorithm:

• Bellman Expectation Equation: Vπ(s) = ∑_a π(a|s) * ∑_{s'} P(s'|s,a) * [R(s,a,s') + γ * Vπ(s')]
• Bellman Optimality Equation: V*(s) = max_a ∑_{s'} P(s'|s,a) * [R(s,a,s') + γ * V*(s')]

Policies

A policy π defines the agent's behavior. It maps states to actions (or probability distributions over actions):

Exploration Strategies

• ε-Greedy: With probability ε, take a random action (explore); otherwise, take the best known action (exploit). Commonly starts with ε=1.0 and decays to 0.01 over training.
• Softmax (Boltzmann): Actions are chosen with probability proportional to their estimated value. Higher-value actions are more likely, but all actions have nonzero probability.
• Upper Confidence Bound (UCB): Choose actions that balance high estimated value with high uncertainty. Prefers actions that haven't been tried much.

import numpy as np

def epsilon_greedy(Q, state, epsilon, num_actions):
    """Select action using epsilon-greedy policy."""
    if np.random.random() < epsilon:
        # Explore: random action
        return np.random.randint(num_actions)
    else:
        # Exploit: best known action
        return np.argmax(Q[state])

# Decay epsilon over time
epsilon_start = 1.0
epsilon_end = 0.01
epsilon_decay = 0.995

epsilon = epsilon_start
for episode in range(1000):
    action = epsilon_greedy(Q, state, epsilon, num_actions=4)
    epsilon = max(epsilon_end, epsilon * epsilon_decay)