5.1 Fundamentals of Reinforcement Learning
Reinforcement Learning (RL) is a machine learning paradigm where an agent learns to make sequential decisions by interacting with an environment to maximize cumulative rewards. Unlike supervised learning, RL uses delayed, sparse rewards and involves exploration of unknown states.
Key Distinctions
| Aspect | Supervised Learning | Unsupervised Learning | Reinforcement Learning |
|---|---|---|---|
| Data | Labeled (input-output pairs) | Unlabeled (find patterns) | Interaction stream (states, actions, rewards) |
| Goal | Minimize prediction error | Discover hidden structure | Maximize long-term reward |
| Feedback | Immediate, explicit | None | Delayed, scalar reward |
| Decision | One-step prediction | Clustering/dimension reduction | Sequential, trial-and-error |
Markov Decision Process (MDP)
The formal framework for RL, defined by tuple $(S, A, P, R, \gamma)$:
-
$S$: Set of states
-
$A$: Set of actions
-
$P(s' \mid s, a)$: Transition probability to state $s'$ from $s$ taking $a$
-
$R(s, a, s')$: Reward function
-
$\gamma \in [0,1]$: Discount factor for future rewards
Policy $\pi(a \mid s)$: Strategy mapping states to actions.
Value functions:
-
State-value: $$\displaystyle V^\pi(s) = \mathbb{E}_\pi \left[ \sum_{t=0}^\infty \gamma^t R_t \mid S_0 = s \right] $$
-
Action-value: $$\displaystyle Q^\pi(s,a) = \mathbb{E}_\pi \left[ \sum_{t=0}^\infty \gamma^t R_t \mid S_0 = s, A_0 = a \right] $$
Solution Methods
- Value Iteration: Iteratively updates $V(s)$ until convergence.
$$V_{k+1}(s) \leftarrow \max_a \sum_{s'} P(s' \mid s,a) \left[ R(s,a,s') + \gamma V_k(s') \right]$$
\boxed{V_{k+1}(s) \leftarrow \max_a \sum_{s'} P(s' \mid s,a) \left[ R(s,a,s') + \gamma V_k(s') \right]}
-
Policy Iteration: Alternates between:
-
Policy Evaluation: Compute $$\displaystyle V^\pi $$ for current $\pi$.
-
Policy Improvement: $$\displaystyle \pi' \leftarrow \arg\max_a \sum_{s'} P(s' \mid s,a) \left[ R(s,a,s') + \gamma V^\pi(s') \right] $$.
-
[!TIP] Value Iteration updates values directly; Policy Iteration explicitly maintains a policy. Both converge to optimal policy for finite MDPs.
Exploration vs Exploitation
-
Exploration: Trying new actions to discover potentially better rewards.
-
Exploitation: Choosing actions with highest known reward.
-
Strategies:
-
$\epsilon$-greedy: With probability $\epsilon$ choose random action; else best action.
-
Softmax: Select action $a$ with probability $$\displaystyle \frac{e^{Q(s,a)/\tau}}{\sum_{a'} e^{Q(s,a')/\tau}} $$, where $\tau$ is temperature.
-
[!TIP] Exploration is critical in RL to avoid suboptimal policies; $\epsilon$-greedy is simple but may not balance optimally.
5.2 Model-Free Methods
Learn directly from experience without environmental model.
Q-learning (Off-Policy)
-
Updates $Q(s,a)$ using max over next actions, independent of current policy.
-
Update rule:
\boxed{Q(s,a) \leftarrow Q(s,a) + \alpha \left[ r + \gamma \max_{a'} Q(s',a') - Q(s,a) \right]}
where $\alpha$ is learning rate.
-
Converges to optimal $$\displaystyle Q^* $$ with sufficient exploration.
SARSA (On-Policy)
-
Updates $Q(s,a)$ using actual next action $a'$ taken by current policy.
-
Update rule:
\boxed{Q(s,a) \leftarrow Q(s,a) + \alpha \left[ r + \gamma Q(s',a') - Q(s,a) \right]}
-
More conservative; learns policy including exploration.
O-Learning
-
Variant of Q-learning with optimistic initialization (e.g., high initial $Q$-values) to encourage early exploration.
-
Often used in optimistic exploration strategies.
Comparison: Q-learning vs SARSA
| Feature | Q-learning | SARSA |
|---|---|---|
| Policy | Off-policy (learns optimal policy) | On-policy (learns current policy) |
| Update Target | $$\displaystyle \max_{a'} Q(s',a') $$ | $Q(s',a')$ from current policy |
| Exploration Handling | Ignores exploration in target | Accounts for exploration |
| Safety | May learn risky shortcuts | Safer in hazardous environments |
| Convergence | To optimal $$\displaystyle Q^* $$ | To $$\displaystyle Q^\pi $$ of exploration policy |
[!TIP] In cliff-walking example, SARSA learns safer path around cliff; Q-learning may jump over cliff due to max operator.
5.3 Actor-Critic Methods
Combine policy-based (actor) and value-based (critic) approaches for better sample efficiency and stability.
Basic Actor-Critic
-
Actor: Policy network $$\displaystyle \pi_\theta(a \mid s) $$ outputs action probabilities.
-
Critic: Value network $$\displaystyle V_w(s) $$ estimates state value.
-
Interaction:
-
Actor selects action $$\displaystyle a \sim \pi_\theta(\cdot \mid s) $$.
-
Environment returns reward $r$ and next state $s'$.
-
Critic computes TD error: $$\displaystyle \delta = r + \gamma V_w(s') - V_w(s) $$.
-
Updates:
-
Critic: Minimize $$\displaystyle \delta^2 $$ (e.g., gradient descent on $w$).
-
Actor: Policy gradient $$\displaystyle \theta \leftarrow \theta + \alpha \delta \nabla_\theta \log \pi_\theta(a \mid s) $$.
-
-
Advanced Models
-
A2C (Advantage Actor-Critic): Uses advantage function $$\displaystyle A(s,a) = Q(s,a) - V(s) $$ to reduce variance. Often implemented with shared network.
-
A3C (Asynchronous Advantage Actor-Critic): Multiple parallel actors with asynchronous gradient updates. Improves training speed and stability.
-
PPO (Proximal Policy Optimization): Uses clipped objective to limit policy updates:
$$L^{CLIP}(\theta) = \mathbb{E} \left[ \min \left( r_t(\theta) \hat{A}_t, \text{clip}(r_t(\theta), 1-\epsilon, 1+\epsilon) \hat{A}_t \right) \right]$$
where $$\displaystyle r_t(\theta) = \frac{\pi_\theta(a_t \mid s_t)}{\pi_{\theta_{\text{old}}}(a_t \mid s_t)} $$, $$\displaystyle \hat{A}_t $$ is advantage estimate, $\epsilon$ is clip range.
[!TIP] Actor-Critic reduces high variance of pure policy gradients while avoiding value function bias. PPO is widely used for stable training.
5.4 Frameworks and Applications
Popular Frameworks
| Framework | Purpose | Key Features |
|---|---|---|
| OpenAI Gym | Standardized RL environments | Unified API (reset(), step()), diverse environments (Classic Control, Atari, Robotics) |
| TensorFlow Agents | Scalable deep RL with TensorFlow | Implementations of DQN, PPO, SAC; integrates with TF ecosystem |
Example with OpenAI Gym:
import gym
env = gym.make('CartPole-v1')
state = env.reset()
for _ in range(1000):
action = agent.select_action(state) # Your policy
next_state, reward, done, _ = env.step(action)
if done: state = env.reset()
Applications
-
Robotics: Motion planning, manipulation (e.g., robotic grasping with sparse rewards).
-
Game Playing: AlphaGo (Go), AlphaStar (StarCraft II), OpenAI Five (Dota 2).
-
Autonomous Systems: Self-driving cars (lane changing, intersection handling), drone navigation.
[!TIP] OpenAI Gym is ideal for prototyping; TensorFlow Agents suits large-scale distributed training.
5.5 Specialized Learning Paradigms
One-Shot Learning
-
Definition: Learning from very few examples (often one per class), contrasting with supervised learning needing thousands.
-
How it differs:
-
Supervised learning: Requires large labeled datasets; poor generalization with few examples.
-
One-shot learning: Uses meta-learning ("learning to learn") to adapt quickly from limited data. Optimizes for fast parameter updates on new tasks.
-
-
Key Approaches:
-
Metric-based: Learn embedding space (e.g., Siamese networks, Prototypical Networks) where similarity is measured.
-
Optimization-based: Model-Agnostic Meta-Learning (MAML) trains model parameters $\theta$ that can adapt to new tasks with few gradient steps.
-
-
Applications:
-
Face recognition (new person with one photo).
-
Rare event detection (e.g., medical diagnosis with few cases).
-
Personalized recommendations with limited user interaction.
-
[!TIP] One-shot learning leverages prior knowledge from similar tasks; MAML is a foundational algorithm enabling quick adaptation.