Mathematical foundations of sequential decision making: Markov Decision Processes (MDP), Bellman expectation and optimality equations, exploration vs. exploitation dynamics, Q-learning temporal difference control, and real-world autonomous systems.
Unlike Supervised Learning (which learns from explicit labeled targets (x, y)) and Unsupervised Learning (which uncovers latent patterns from unlabelled data), Reinforcement Learning (RL) is a computational framework for goal-directed learning from trial-and-error interactions. An autonomous entity (the Agent) learns an optimal strategy by interacting with a dynamic, uncertain Environment.
π)S_t in S; selects action A_t in A according to its policy π(a mid s).A_t TransmittedP(s' mid s, a) and emits scalar reward Rt+1.St+1 & Rt+1Rt+1 in R and new state St+1 for the next cycle.
The mathematical formalization of an RL environment is a Markov Decision Process (MDP), defined by the 5-tuple (S, A, P, R, γ):
| MDP Component | Mathematical Notation | Definition & Operational Semantics |
|---|---|---|
| State Space | s in S |
Complete description of the current environmental configuration satisfying the Markov Property: P(St+1 mid S_t, A_t, St-1, At-1, dots) = P(St+1 mid S_t, A_t). The future depends only on the present, not the past. |
| Action Space | a in A or A(s) |
Set of valid decisions available to the agent (discrete, e.g., {0, 1, 2, 3 }, or continuous vector spaces, e.g., torque angles in R^D). |
| Transition Probability | Ps, s'^a = P(St+1 = s' mid S_t = s, A_t = a) |
Stochastic probability distribution governing which state s' the environment transitions to when action a is executed from state s. |
| Reward Function | R(s, a, s') = E[Rt+1 mid S_t = s, A_t = a, St+1 = s'] |
Scalar feedback signal measuring immediate success or penalty. |
| Discount Factor | γ in [0, 1) |
Quantifies the present value of future rewards. Ensures mathematical convergence of infinite-horizon returns and reflects uncertainty about the distant future. |
An RL agent does not simply maximize immediate reward Rt+1; it seeks to maximize the Expected Discounted Cumulative Return G_t from time step t onward:
New Q-Value(State, Action) = Current Q-Value + Learning Rate × [TD Target − Current Q-Value](s, a) are visited infinitely often, and the learning rate satisfies the Robbins-Monro conditions Sum t=1^infty α_t = infty and Sum t=1^infty α_t^2 < infty, then Q(s, a) converges with probability 1 to the true optimal action-value function Q^*(s, a) as t → infty.
| Application Domain | State Space (S) |
Action Space (A) |
Reward Function (R) |
Industry Milestone |
|---|---|---|---|---|
| LLM Alignment (RLHF / PPO) | Prompt text token history + generated tokens. | Next token distribution generation. | Scalar score from a human preference Reward Model. | InstructGPT, ChatGPT, Claude, and Gemini alignment. |
| Autonomous Vehicles | LiDAR point clouds, camera feeds, velocity, trajectory. | Continuous steering torque, brake pressure, throttle. | +1 per safe meter; severe penalty for lane departures and collisions. |
Waymo, Tesla FSD path planning and trajectory optimization. |
| Complex Strategy Games | Board pixel matrices or piece positions. | Valid moves / micro-action coordinates. | +1 for victory, -1 for defeat, 0 otherwise. |
DeepMind AlphaGo, AlphaZero, and StarCraft II AlphaStar. |
| Quantitative Trading | Order book depth, price momentum, portfolio holdings. | Market orders: Buy, Hold, Sell, position size. | Risk-adjusted return (Sharpe Ratio), P&L after fees. | High-frequency algorithmic market making and execution. |
| Data Center Cooling | Server thermal sensors, power load, ambient weather. | Cooling pump speeds, airflow fan speeds, chillers. | Negative energy consumption (PUE reduction). | Google DeepMind cut data center cooling energy costs by 40 %. |
The following self-contained script implements an autonomous RL agent navigating a stochastic 4 × 4 GridWorld environment with pitfalls, moving obstacles, and a terminal goal. It implements the complete Bellman TD Q-Learning update rule, an ε-decay schedule, policy convergence tracking, and policy path extraction with pure white syntax contrast (`#ffffff !important`).
# =====================================================================
# DevAscent Academy: Production Q-Learning GridWorld Simulation Engine
# Requires: numpy, pandas
# =====================================================================
import numpy as np
import pandas as pd
class GridWorldEnvironment:
"""
A 4x4 GridWorld Markov Decision Process (MDP):
S: Start at (0, 0)
G: Goal at (3, 3) -> Reward +10.0, Terminal
P: Pitfalls at (1, 1) and (2, 3) -> Reward -10.0, Terminal
Actions: 0: UP, 1: DOWN, 2: LEFT, 3: RIGHT
Step Penalty: -0.1 (encourages shortest path)
"""
def __init__(self, size=4):
self.size = size
self.n_states = size * size
self.n_actions = 4
self.goal_state = 15 # (3, 3)
self.pitfall_states = [5, 11] # (1, 1) and (2, 3)
self.reset()
def reset(self):
self.current_state = 0 # Start at top-left
return self.current_state
def step(self, action):
r = self.current_state // self.size
c = self.current_state % self.size
# Action Execution Mechanics
if action == 0: # UP
r = max(0, r - 1)
elif action == 1: # DOWN
r = min(self.size - 1, r + 1)
elif action == 2: # LEFT
c = max(0, c - 1)
elif action == 3: # RIGHT
c = min(self.size - 1, c + 1)
next_state = r * self.size + c
# Evaluate Rewards and Terminal State
if next_state == self.goal_state:
reward = 10.0
done = True
elif next_state in self.pitfall_states:
reward = -10.0
done = True
else:
reward = -0.1 # Step penalty
done = False
self.current_state = next_state
return next_state, reward, done
class QLearningAgent:
def __init__(self, n_states, n_actions, lr=0.1, gamma=0.95, epsilon=1.0, epsilon_decay=0.995, epsilon_min=0.01):
self.n_states = n_states
self.n_actions = n_actions
self.lr = lr
self.gamma = gamma
self.epsilon = epsilon
self.epsilon_decay = epsilon_decay
self.epsilon_min = epsilon_min
# Initialize Q-Table with zeros: Shape (16, 4)
self.q_table = np.zeros((n_states, n_actions))
def choose_action(self, state):
"""Epsilon-Greedy Action Selection Policy"""
if np.random.rand() < self.epsilon:
return np.random.randint(self.n_actions) # Explore
else:
# Exploit: Pick greedy action with random tie-breaking
q_vals = self.q_table[state]
max_q = np.max(q_vals)
best_actions = np.where(q_vals == max_q)[0]
return np.random.choice(best_actions)
def update(self, state, action, reward, next_state, done):
"""Bellman Temporal Difference Update"""
current_q = self.q_table[state, action]
if done:
td_target = reward
else:
# Off-policy: max over all possible next actions
td_target = reward + self.gamma * np.max(self.q_table[next_state])
# Q-Learning TD update step
self.q_table[state, action] += self.lr * (td_target - current_q)
def decay_epsilon(self):
self.epsilon = max(self.epsilon_min, self.epsilon * self.epsilon_decay)
def run_reinforcement_learning_pipeline():
# -----------------------------------------------------------------
# 1. Environment & Agent Initialization
# -----------------------------------------------------------------
env = GridWorldEnvironment(size=4)
agent = QLearningAgent(
n_states=env.n_states,
n_actions=env.n_actions,
lr=0.15,
gamma=0.95,
epsilon=1.0,
epsilon_decay=0.992,
epsilon_min=0.01
)
n_episodes = 800
episode_rewards = []
goal_reaches = 0
print(f"[Simulation] Starting Q-Learning Training across {n_episodes} Episodes...")
# -----------------------------------------------------------------
# 2. Episode Training Loop
# -----------------------------------------------------------------
for ep in range(n_episodes):
state = env.reset()
total_reward = 0.0
done = False
steps = 0
while not done and steps < 60:
action = agent.choose_action(state)
next_state, reward, done = env.step(action)
agent.update(state, action, reward, next_state, done)
state = next_state
total_reward += reward
steps += 1
if done and next_state == env.goal_state:
goal_reaches += 1
agent.decay_epsilon()
episode_rewards.append(total_reward)
print(f"[Training Complete] Successful Goal Reaches: {goal_reaches} of {n_episodes} runs.")
print(f"Final Epsilon (Exploration Rate): {agent.epsilon:.4f}")
# -----------------------------------------------------------------
# 3. Inspect Converged Q-Table & Derive Optimal Policy
# -----------------------------------------------------------------
print("\n--- [Phase 1] Converged Q-Table (First 6 States) ---")
action_names = ['UP', 'DOWN', 'LEFT', 'RIGHT']
q_df = pd.DataFrame(agent.q_table[:6], columns=action_names)
q_df.index = [f"State {i}" for i in range(6)]
print(q_df.round(3).to_string())
# -----------------------------------------------------------------
# 4. Extract & Visualize Optimal Trajectory (Zero-Epsilon Evaluation)
# -----------------------------------------------------------------
print("\n--- [Phase 2] Optimal Autonomous Path Execution ---")
agent.epsilon = 0.0 # Pure exploitation (Greedy)
curr_state = env.reset()
path = [curr_state]
actions_taken = []
eval_reward = 0.0
done = False
step_count = 0
while not done and step_count < 20:
action = agent.choose_action(curr_state)
actions_taken.append(action_names[action])
next_state, reward, done = env.step(action)
path.append(next_state)
eval_reward += reward
curr_state = next_state
step_count += 1
path_coords = [(s // 4, s % 4) for s in path]
print(f"Trajectory Path (State IDs): {path}")
print(f"Trajectory Grid Coordinates: {path_coords}")
print(f"Actions Sequence: {' -> '.join(actions_taken)}")
print(f"Total Cumulative Return: {eval_reward:.2f} (Target Reached: {curr_state == env.goal_state})")
if __name__ == '__main__':
run_reinforcement_learning_pipeline()
S_t satisfies the Markov Property if and only if:
P(St+1 = s', Rt+1 = r mid S_t, A_t, St-1, At-1, dots, S_0, A_0) = P(St+1 = s', Rt+1 = r mid S_t, A_t)S_t summarizes all relevant information from the past. Given the current state, future transitions and rewards are conditionally independent of the historical path taken to reach it. This assumption enables recursive Dynamic Programming and Bellman equations, since optimal actions can be computed without retaining the entire history of previous interactions.
Q(S, A) ← Q(S, A) + α [R + γ Q(S', A') - Q(S, A)], where A' is the actual action chosen by the current behavior policy (ε-greedy). In contrast, Q-Learning updates using the maximum Q-value in the next state: maxa' Q(S', a'). This assumes an optimal greedy policy regardless of which exploratory action the agent actually takes in the environment. Because the target policy (greedy) differs from the behavior policy (ε-greedy), Q-learning is off-policy.
γ = 0 versus when γ → 1?
G_t = Sum k=0^infty γ^k Rt+k+1. When γ = 0, the agent becomes myopic ("short-sighted"): it maximizes only the immediate reward Rt+1, completely ignoring future consequences. When γ → 1, the agent becomes far-sighted: future rewards are weighted nearly equally with immediate rewards. In continuing tasks with infinite horizons, γ < 1 is mathematically required to ensure that the infinite geometric series converges to a finite value.
V^π), and (2) Policy Improvement, which updates the policy greedily with respect to the new values (π'(s) = arg max_a Sum P [r + γ V(s')]). Value Iteration combines these steps into a single update per iteration using the Bellman Optimality Equation: Vk+1(s) = max_a Sum P [r + γ V_k(s')]. It updates state values greedily without waiting for policy evaluation to converge.
|S| × |A|. For raw video frames (84 × 84 pixels with 256 colors), the number of possible states exceeds 2567056, making table storage and visit coverage physically impossible. Deep Q-Networks (DQN) (Mnih et al., 2015) replace the lookup table with a deep neural network function approximator Q(s, a; θ) ≈ Q^*(s, a). DQN stabilizes neural network training using two key mechanisms: (1) Experience Replay, which breaks temporal correlations by randomly sampling transitions (s, a, r, s') from a replay buffer, and (2) a Target Network (θ^-) with delayed parameter updates, which prevents training instabilities caused by moving target values.
arg maxa in A Q(s, a). When the action space A is continuous (e.g., multi-joint motor torques in R^6), finding the global maximum requires solving a non-convex continuous optimization problem at every time step, which is computationally impractical. Policy Gradient methods (e.g., REINFORCE, PPO, SAC) parameterize the policy directly (π_θ(a mid s)) and optimize expected return via gradient ascent (∇_θ J(θ) = E[∇_θ log π_θ(a mid s) Q(s, a)]). This allows sampling continuous actions directly from learned probability distributions without discrete maximization steps.
F(s, s') = γ Phi(s') - Phi(s), which is mathematically proven not to alter the optimal policy.
π_φ is optimized to maximize a scalar reward R(x, y) predicted by a learned Reward Model. Without regularization, the model will exploit flaws in the reward model (Reward Model Over-optimization), producing repetitive or nonsensical text that scores high on the reward model. To prevent this, PPO optimizes:
max_φ E(x, y) follows D [ R(x, y) - β DKL( π_φ(y mid x) , , πref(y mid x) right) right]DKL penalizes the model when its output token distribution drifts too far from the original frozen reference model πref, ensuring the aligned model retains language coherence while following human preferences.