15. Elements of Reinforcement Learning

This lesson formalizes the key components of the RL framework: policies, value functions, and the role of the discount factor in shaping agent behavior.

Policies

A policy pi defines the agent's behavior:

• Deterministic policy: a = pi(s) — maps state to action directly
• Stochastic policy: a ~ pi(a|s) — probability distribution over actions
• Optimal policy: pi* = argmax_pi V^pi(s) for all s

Value Functions

The state-value function under policy pi: V^pi(s) = E_pi[sum(gamma^t * r_t) | s_0 = s]

The action-value (Q) function under policy pi: Q^pi(s, a) = E_pi[sum(gamma^t * r_t) | s_0 = s, a_0 = a]

Relationship: V^pi(s) = sum_a pi(a|s) * Q^pi(s, a)

Bellman Equations

The Bellman expectation equations provide recursive characterizations: V^pi(s) = sum_a pi(a|s) sum_s' P(s'|s,a) [r(s,a,s') + gamma * V^pi(s')]

Q^pi(s,a) = sum_s' P(s'|s,a) [r(s,a,s') + gamma sum_a' pi(a'|s') * Q^pi(s',a')]

The Discount Factor Gamma

gamma controls how much the agent values future rewards:

Exploration vs Exploitation

• Exploitation: Take the best known action (greedy)
• Exploration: Try new actions to discover potentially better strategies

epsilon-greedy strategy: With probability epsilon, take a random action; otherwise greedy.

Common Pitfalls

• Discount factor too small: agent ignores long-term consequences and behaves myopically
• No exploration: agent gets stuck in a locally optimal policy (exploitation trap)
• Wrong reward shaping can lead to unintended optimal behaviors (reward hacking)

Exam-Ready Summary

• Policy pi(a|s): defines action selection; can be deterministic or stochastic
• Value function V^pi(s): expected discounted return from state s under policy pi
• Q-function Q^pi(s,a): expected return from (state, action) pair, then following pi
• Bellman equation: recursive characterization linking value at s to values at successor states
• Discount factor gamma near 1 encourages planning; near 0 encourages myopic behavior