Lecture 11: Reinforcement Learning

HTML Slides | PDF Slides

(Deep) Reinforcement Learning

COMP 4630 | Winter 2026 Charlotte Curtis

Overview

• Terminology and fundamentals
• Q-learning
• Deep Q Networks
• References and suggested reading:
  • Scikit-learn book: Chapter 18
  • d2l.ai: Chapter 17

Reinforcement Learning + LLMs

Terminology

• Agent: the learner or decision maker
• Environment: the world the agent interacts with
• State: the current situation
• Reward: feedback from the environment
• Action: what the agent can do
• Policy: the strategy the agent uses to make decisions

Classic example: Cartpole

The Credit Assignment Problem

• Problem: If we’ve taken 100 actions and received a reward, which ones were “good” actions contributing to the reward?
• Solution: Evaluate an action based on the sum of all future rewards
  • Apply a discount factor $\gamma$ to future rewards, reducing their influence
  • Common choice in the range of $\gamma =0.9$ to $\gamma =0.99$
  • Example of actions/rewards:
    • Action: Right, Reward: 10
    • Action: Right, Reward: 0
    • Action: Right, Reward: -50

Policy Gradient Approach

• If we can calculate the gradient of the expected reward with respect to the policy parameters, we can use gradient descent to find the best policy
• Loss function example: REINFORCE (Williams, 1992) $$\mathcal{L}(\theta )=-\sum _t\log {\pi }_{\theta }(a_t|s_t)\cdot r_t$$ where:
  • ${\pi }_{\theta }(a_t|s_t)$ = output probability for action $a_t$ given state $s_t$
  • $r_t$ = reward at timestep $t$
  • $\theta$ = model parameters

Value-based methods

• Policy gradient approach is direct, but only really works for simple policies
• Value-based methods instead explore the space and learn the value associated with a given action
• Based on Markov Decision Processes (review from AI?)

Markov Chains

• A Markov Chain is a model of random states where the future state depends only on the current state (a memoryless process)
• Used to model real-world processes, e.g. Google’s PageRank algorithm
• ❓ Which of these is the terminal state?

Markov Decision Processes

• Like a Markov Chain, but with actions and rewards
• Bellman optimality equation: $$V^{\ast }(s)=\underset{a}{\max }\sum _{s^{\prime }}T(s,a,s^{\prime })[R(s,a,s^{\prime })+\gamma V^{\ast }(s^{\prime })]\text{ for all }s$$

Iterative solution to Bellman’s equation

Value Iteration:

1. Initialize $V(s)=0$ for all states
2. Update $V(s)$ using the Bellman equation
3. Repeat until convergence

$$V_{k+1}(s)\leftarrow \underset{a}{\max }\sum _{s^{\prime }}T(s,a,s^{\prime })[R(s,a,s^{\prime })+\gamma V_k(s^{\prime })]\text{ for all }s$$

Problem: we still don’t know the optimal policy

Q-Values

Bellman’s equation for Q-values (optimal state-action pairs):

$$Q_{k+1}(s,a)\leftarrow \sum _{s^{\prime }}T(s,a,s^{\prime })[R(s,a,s^{\prime })+\gamma \underset{a^{\prime }}{\max }{Q}_k(s^{\prime },a^{\prime })]$$

Optimal policy ${\pi }^{\ast }(s)$:

$${\pi }^{\ast }(s)=\arg \underset{a}{\max }{Q}^{\ast }(s,a)$$

For small spaces, we can use dynamic programming to iteratively solve for $Q^{\ast }$

Q-Learning

• Q-Learning is a variation on Q-value iteration that learns the transition probabilities and rewards from experience
• An agent interacts with the environment and keeps track of the estimated Q-values for each state-action pair
• It’s also a type of temporal difference learning (TD learning), which is kind of similar to stochastic gradient descent
• Interestingly, Q-learning is “off-policy” because it learns the optimal policy while following a different one (in this case, totally random exploration)

Q-Learning Update rule

• At each iteration, the Q estimate is updated according to: $$Q(s,a)\leftarrow (1-\alpha )\cdot Q(s,a)+\alpha \cdot [r+\gamma \cdot \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime })]$$

• Where:

  • $Q(s,a)$ is the estimated value of taking action $a$ in state $s$
  • $\alpha$ is the learning rate (decreasing over time)
  • $r$ is the immediate reward
  • $\gamma$ is the discount factor
  • ${\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })$ is the maximum Q-value for the next state

Exploration policies

• ❓ How do you balance short-term rewards, long-term rewards, and exploration?
• Our small example used a purely random policy
• $ϵ$-greedy chooses to explore randomly with probability $ϵ$, and greedily with probability $1-ϵ$
• Common to start with high $epsilon$ and gradually reduce (e.g. 1 down to 0.05)

Challenges with Q-Learning

• ❓ We just converged on a 3-state problem in 10k iterations. How many states are in something like an Atari game?
• ❓ How do we handle continuous state spaces?

Deep Q-Networks

• We know states, actions, and observed rewards
• We need to estimate the Q-values for each state-action pair
• Target Q-values: $y(s,a)=r+\gamma \cdot {\max }_{a^{\prime }}{Q}_{\theta }(s^{\prime },a^{\prime })$
  • $r$ is the observed reward, $s^{\prime }$ is the next state
  • $Q_{\theta }(s^{\prime },a^{\prime })$ is the network’s estimate of the future reward
• Loss function: $\mathcal{L}(\theta )=||y(s,a)-Q_{\theta }(s,a)|{|}^2$
• Standard MSE, backpropagation, etc.

Challenges with DQNs

• Catastrophic forgetting: just when it seems to converge, the network forgets what it learned about old states and comes crashing down
• The learning environment keeps changing, which isn’t great for gradient descent
• The loss value isn’t a good indicator of performance, particularly since we’re estimating both the target and the Q-values
• Ultimately, reinforcement learning is inherently unstable!

The last topic: Geneterative AI and ethics

GenAI + Ethics Discussion

• Generative images have gotten really good
• What can we do? What should we do?