Q-Learning

Intro

Q-learning is a model-free Reinforcement Learning algorithm that learns an action-value function Q(s,a), estimating the expected cumulative reward of taking action $a$ in state $s$. Its objective is to find the optimal policy that maximizes long-term reward in a Markov Decision Process (MDP).

It enables an agent to learn optimal actions through trial-and-error by interacting with the environment, without requiring knowledge of the transition function or reward model. Q-values are stored in a Q-table (or approximated with a function) and are updated iteratively using the Bellman update rule until convergence to the optimal policy.

Instead of learning the environment, Q-learning learns:

“How good is it to take action a in state s?”

---

Q-Function

Q-learning learns the value function: ¹

$$Q(s,a)$$

which estimates the expected cumulative reward of taking action $a$ in state $s$.

The optimal Policy is derived as:

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

ε-greedy Policy

The ε-greedy policy is used during training to balance exploration and exploitation:

• with probability $ϵ$ → choose a random action (explore)
• with probability $1-ϵ$ → choose the best known action (exploit)

$$a=\{\begin{array}{llc}\text{random action}& \text{with probability }ϵ\arg {\max }_{a}Q(s,a)& \text{with probability }1-ϵ\end{array}$$

import numpy as np
 
def select_action(q_values, epsilon, n_actions):
    # With probability epsilon - explore
    if np.random.rand() < epsilon:
        return np.random.randint(n_actions)
    # With probability 1 - epsilon - exploit
    else:
        return np.argmax(q_values)
 

Update Rule

Q-learning gradually shifts old estimates toward new evidence, balancing prior knowledge with newly observed outcomes.

$$Q(s,a)\leftarrow Q(s,a)+\alpha \left[r+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime })-Q(s,a)\right]$$

Where:

• α = learning rate (Update speed- controls how much new info overrides old Q)
• γ = discount factor (importance of future reward)
• r = immediate reward
• s’ = next state
• max Q(s’,a’) = best possible future value

---

Q-Learning Hyperparameters

Learning Rate ($\alpha$)

Range:

$$0\le \alpha \le 1$$

Controls how much new information overrides old Q-values.

Effect:

• High ($\alpha \approx 0.9$) → fast learning, unstable updates
• Low ($\alpha \approx 0.1$) → slow but stable learning

---

Discount Factor ($\gamma$)

Range:

$$0\le \gamma \le 1$$

Controls importance of future rewards vs immediate rewards.

Effect:

• $\gamma \approx 0$ → only immediate reward matters (short-sighted)
• $\gamma \approx 1$ → long-term rewards matter heavily (far-sighted)

---

Exploration Rate ($ϵ$)

Range:

$$0\le ϵ\le 1$$

Controls probability of choosing a random action instead of the best-known action.

Effect:

• High ($ϵ$) → more exploration
• Low ($ϵ$) → more exploitation

Typically:

$ϵ$ starts high and decays over time as the agent learns

---

Parameter Overview

Parameter	Name	What it Controls	Effect
$\alpha$	Learning Rate	How fast Q-values update	Speed vs stability
$\gamma$	Discount Factor	Importance of future rewards	Short-term vs long-term planning
$ϵ$	Exploration Rate	Random vs greedy actions	Exploration vs exploitation

Tuning Recommendationn (Millington)

• Learning Rate: 0.3 (Can vary from 0.1 to 0.7)
• Discount Rate: 0.75
• Randomness for exploration
  • Online: 0.1
  • Offline: 0.2

Algorithm

Q-learning iteratively updates the current Q-value by blending it with a target value made from the immediate reward plus the estimated best future value of the next state.

1. Initialize Q(s,a) arbitrarily
2. Observe current state s
3. Choose action a (ε-greedy)
4. Execute action, observe r and s’
5. Update Q(s,a)
6. Set s ← s’
7. Repeat

Performance

• Time Complexity: $O(i)$- Where i is number of learning iterations
• Space complexity: $O(SA)$- Where $S$ = number of states and $A$ = number of actions

Footnotes

1. https://cs50.harvard.edu/ai/notes/4/#q-learning ↩