Reinforcement Learning Mdp Policy Value Functions
# Reinforcement Learning: MDP, Policy & Value Functions
## Introduction & Motivation
RL learns optimal policies via interaction. Agent receives state, takes action, gets reward, transitions to next state. Markov Decision Process (MDP) formalizes: S (states), A (actions), P (transitions), R (rewards), γ (discount). Value function V(s) estimates long-term reward; Q(s,a) estimates action value.
Motivation: Learn decision-making from trial-and-error without explicit supervised labels. Exploration-exploitation tradeoff; temporal credit assignment.
Applications: Game playing, robotics, autonomous driving, resource allocation.
---
## Core Concepts & Theory
### Markov Decision Process
States, actions, transition probabilities, rewards. Memoryless (Markov property): P(s'|s,a) independent of history.
### Policy & Value Function
Policy π(a|s): action selection probability given state.
Value V(s): expected cumulative discounted reward from state s under π.
Q(s,a): expected cumulative reward from (s,a) under π.
### Bellman Equation
V(s) = E[R(s,a) + γ V(s')].
Expresses value recursively; foundation for DP, Q-learning.
---
## Mathematical Formulation
Return (cumulative discounted reward):
$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \ldots = \sum_{k=0}^\infty \gamma^k R_{t+k+1}$$
State value function:
$$V^\pi(s) = \mathbb{E}_\pi[G_t | S_t = s] = \mathbb{E}_\pi[R_{t+1} + \gamma V^\pi(S_{t+1}) | S_t = s]$$
Action value function:
$$Q^\pi(s,a) = \mathbb{E}_\pi[R_{t+1} + \gamma V^\pi(S_{t+1}) | S_t = s, A_t = a]$$
Optimal policy:
$$\pi^*(a|s) = \arg\max_a Q^*(s,a)$$
---
## Advanced Theory & Extensions
### Temporal Difference Learning
Update V(s) based on TD error: V(s) ← V(s) + α[R + γV(s') - V(s)].
Bootstraps from next state estimate; reduces variance vs. Monte Carlo.
### Actor-Critic Methods
Separate policy (actor) and value (critic) networks. Actor updates via policy gradient; critic via TD error.
---
## Computational Considerations
Tabular methods: O(|S||A|) memory; convergence in polynomial time for finite MDPs.
Function approximation: Scales to large/continuous spaces; convergence guarantees weaker.
Exploration: ε-greedy, softmax, upper confidence bound (UCB).
---
## Practical Implementation Strategies
### Discount Factor γ
Typical 0.99 (near-sighted). Higher = long-horizon; lower = short-term focus.
### Learning Rate α
Decay schedule: α_t = α_0 / (1 + t). Ensures convergence.
### Exploration Decay
Start high ε, decay to low. Balance exploration early; exploitation later.
---
## Benchmark Environments & Evaluation
CartPole: Pole balancing; simple discrete task.
Atari: High-dimensional visual states; challenging control.
MuJoCo: Continuous control; robotics simulation.
Metrics: Cumulative return, convergence speed, sample efficiency.
---
## Key Challenges & Limitations
### Exploration-Exploitation
Greedy exploitation ignores better actions; pure exploration is inefficient.
### Non-Stationary Environments
If environment changes, learned policy becomes suboptimal.
### Sparse Rewards
Few reward signals make learning difficult; requires reward shaping or hierarchical approaches.
---
## Hyperparameter Tuning
α (learning rate): 0.01-0.1; decay over time.
γ (discount): 0.99-0.999; long-horizon.
ε (exploration): Start 0.1-1.0; decay to 0.01-0.05.
---
## Real-World Applications & Case Studies
AlphaGo: Deep Q-Networks + tree search; master-level Go.
Robotics: Sim-to-real transfer; manipulation tasks.
Trading: Portfolio optimization via RL agents.
---
## Integration with Other Methods
RL + Deep Learning → DQN, Policy Gradients, Actor-Critic.
RL + Planning → Model-based RL, AlphaGo-style tree search.
---
## Summary & Key Takeaways
RL learns optimal policies via MDPs, value functions, and temporal credit assignment, enabling sequential decision-making from interaction.
Principles:
1. MDP formalizes sequential decision problems.
2. Value function estimates long-term reward.
3. Bellman equation relates value recursively.
4. Temporal difference combines DP and Monte Carlo.
5. Policy gradient enables continuous action spaces.
---
---
## Appendix: Practical Labs
### Lab 1: Q-Learning on GridWorld
import numpy as np
from collections import defaultdict
class GridWorld:
def __init__(self, size=5):
self.size = size
self.start = (0, 0)
self.goal = (size-1, size-1)
self.state = self.start
def reset(self):
self.state = self.start
return self.state
def step(self, action):
x, y = self.state
actions = {0: (-1, 0), 1: (1, 0), 2: (0, -1), 3: (0, 1)}
dx, dy = actions[action]
nx, ny = max(0, min(self.size-1, x+dx)), max(0, min(self.size-1, y+dy))
self.state = (nx, ny)
reward = 1.0 if self.state == self.goal else -0.01
done = self.state == self.goal
return self.state, reward, done
env = GridWorld(size=5)
Q = defaultdict(lambda: np.zeros(4))
alpha, gamma, epsilon = 0.1, 0.99, 0.1
for episode in range(100):
state = env.reset()
for step in range(20):
if np.random.rand() < epsilon:
action = np.random.randint(4)
else:
action = np.argmax(Q[state])
next_state, reward, done = env.step(action)
Q[state][action] += alpha * (reward + gamma * np.max(Q[next_state]) - Q[state][action])
state = next_state
if done:
break
total_states = len(Q)
print(f"Total visited states: {total_states}")
assert total_states > 5, "Should explore multiple states"
assert all(np.max(Q[s]) >= 0 for s in Q), "Q-values should be learned"
print("✓ Q-Learning working")
if __name__ == "__main__":
print("Lab 1: Q-Learning - PASSED")### Lab 2: Policy Evaluation
import numpy as np
def policy_evaluation(states, actions, transitions, rewards, gamma=0.99, iterations=100):
V = {s: 0 for s in states}
for _ in range(iterations):
delta = 0
for s in states:
v_old = V[s]
v_new = 0
for a in actions:
if (s, a) in transitions:
prob, s_next = transitions[(s, a)], rewards[(s, a)]
v_new += prob * (s_next + gamma * V.get(s_next, 0))
V[s] = v_new
delta = max(delta, abs(v_old - v_new))
if delta < 1e-6:
break
return V
states = [0, 1, 2, 3, 4]
actions = [0, 1]
transitions = {(0, 0): (1.0, 1), (1, 0): (1.0, 2), (2, 0): (1.0, 3), (3, 0): (1.0, 4), (4, 0): (1.0, 4)}
rewards = {(0, 0): 0, (1, 0): 1, (2, 0): 1, (3, 0): 1, (4, 0): 10}
V = policy_evaluation(states, actions, transitions, rewards)
print(f"Value estimates: {V}")
assert len(V) == 5, "Should estimate all states"
assert V[4] > V[3], "Terminal state should have higher value"
print("✓ Policy evaluation working")
if __name__ == "__main__":
print("Lab 2: Policy Eval - PASSED")### Lab 3: Temporal Difference Error
import numpy as np
class SimpleEnv:
def reset(self):
return 0
def step(self, state):
return state + 1, state % 2, state >= 4
V = {i: 0 for i in range(5)}
alpha, gamma = 0.1, 0.99
td_errors = []
state = 0
for step in range(50):
action = 0
next_state, reward, done = SimpleEnv().step(state)
td_error = reward + gamma * V.get(next_state, 0) - V[state]
V[state] += alpha * td_error
td_errors.append(abs(td_error))
state = next_state if not done else 0
mean_td_error = np.mean(td_errors)
print(f"Mean absolute TD error: {mean_td_error:.4f}")
assert len(td_errors) > 0, "Should have TD errors"
assert all(e >= 0 for e in td_errors), "Errors should be non-negative"
print("✓ TD error working")
if __name__ == "__main__":
print("Lab 3: TD Error - PASSED")### Lab 4: Value Iteration
import numpy as np
def value_iteration(states, actions, transitions, rewards, gamma=0.99, iterations=100):
V = {s: 0 for s in states}
for _ in range(iterations):
delta = 0
for s in states:
v_old = V[s]
max_v = -np.inf
for a in actions:
if (s, a) in transitions:
prob, s_next = transitions[(s, a)], rewards[(s, a)]
v_candidate = prob * (s_next + gamma * V.get(s_next, 0))
max_v = max(max_v, v_candidate)
V[s] = max_v if max_v > -np.inf else 0
delta = max(delta, abs(v_old - V[s]))
if delta < 1e-6:
break
return V
states = list(range(10))
actions = [0, 1]
transitions = {(s, 0): (1.0, min(s+1, 9)) for s in states}
rewards = {(s, 0): 0 if s < 9 else 100 for s in states}
V = value_iteration(states, actions, transitions, rewards)
print(f"Optimal values: {list(V.values())[:5]}")
assert len(V) == 10, "Should have values for all states"
assert V[9] > V[8], "Goal state should have highest value"
print("✓ Value iteration working")
if __name__ == "__main__":
print("Lab 4: Value Iteration - PASSED")