Q-Learning is a powerful model-free reinforcement learning algorithm that learns the optimal action-value function directly without requiring a model of the environment.

Understanding Model-Based vs. Model-Free Approaches

Model-Based Reinforcement Learning

A model of the environment in reinforcement learning refers to explicit knowledge of the system dynamics, specifically:

  • State Transition Probabilities: $p_{ij}(u)$ - The probability of transitioning from state $i$ to state $j$ when taking action $u$
  • Reward/Cost Functions: $g(i,u,j)$ - The immediate reward or cost received when transitioning from state $i$ to state $j$ via action $u$

With a complete model, we can use dynamic programming methods like value iteration or policy iteration to compute optimal policies without direct environment interaction.

Model-Free Reinforcement Learning

In contrast, model-free methods like Q-Learning operate without requiring explicit knowledge of transition probabilities or reward functions. These approaches:

  • Learn directly from interactions with the environment
  • Update value estimates based on experienced transitions and rewards
  • Do not attempt to build an internal model of how the environment works

Model-free methods excel when:

  • Environment dynamics are unknown or difficult to model
  • The state space is large, making explicit modeling computationally intractable
  • The environment is non-stationary (changing over time)

Q-Learning exemplifies this model-free approach by learning optimal action values through direct experience, without needing to know how the environment will respond to actions beforehand.

SMDP Setting

In the context of Stochastic Shortest Path Problems (SSPP), let’s recall the Bellman equation:

$$ J^*(i) = \min_{u \in A(i)} \sum_{j \in S} p_{ij}(u) \left( g(i,u,j) + J^*(j) \right) \tag{1} $$
where:
  • $J^*(i)$ is the optimal cost-to-go from state $i$
  • $A(i)$ is the set of actions available in state $i$
  • $p_{ij}(u)$ is the transition probability from state $i$ to state $j$ when taking action $u$
  • $g(i,u,j)$ is the immediate cost when transitioning from state $i$ to state $j$ via action $u$

Note that this formulation can also accommodate discount factors for infinite horizon problems.

The Q-Function Definition

Let’s define the optimal Q-function (action-value function) as:

$$ Q^*(i,u) = \sum_{j \in S} p_{ij}(u) \left( g(i,u,j) + J^*(j) \right) \tag{2} $$

This represents the expected total cost when taking action $u$ in state $i$ and following the optimal policy thereafter.

From $(1)$ and $(2)$, we have:

$$ J^*(i) = \min_{u \in A(i)} Q^*(i,u) \tag{3} $$

Note that $Q$ is a function of both the state and action, whereas $J$ is a function of only the state. This additional action dimension in the Q-function allows us to evaluate the quality of specific actions in each state without requiring a model of the environment.

The Q-Bellman Equation

The Q-function satisfies its own Bellman equation (also called the Q-Bellman equation):

$$ Q^*(i,u) = \sum_{j=1}^n p_{ij}(u) \left( g(i,u,j) + \min_{v \in A(j)} Q^*(j,v) \right) \tag{4} $$

This recursive relationship forms the foundation of Q-learning, allowing us to learn optimal behaviors without knowing the transition probabilities or reward functions.

Q-Learning Algorithm

Q-learning is a model-free reinforcement learning algorithm that directly approximates the optimal Q-function without requiring knowledge of the transition probabilities or reward functions. It is an off-policy algorithm, meaning it can learn from actions that are outside the current policy being evaluated.

Numerical Scheme for solving the Bellman Equation

The Q-learning algorithm uses an iterative approach to solve the Q-Bellman equation. The numerical scheme is as follows:

  1. Initialize the Q-function arbitrarily for all state-action pairs:

    $$ \underbrace{Q_0(i,u)}_{\substack{\text{Initial Q-values} \\ \text{for all state-action pairs}}} \text{ for all } i \in S, u \in A(i) $$

    A common initialization is to set all Q-values to zero or to small random values.

  2. For each iteration $m = 0, 1, 2, \ldots$, update the Q-function using the following rule:

    $$ \underbrace{Q_{m+1}(i,u)}_{\substack{\text{Updated Q-value} \\ \text{at iteration } m+1}} = \sum_{j=1}^n \underbrace{p_{ij}(u)}_{\substack{\text{Transition} \\ \text{probability}}} \left( \underbrace{g(i,u,j)}_{\substack{\text{Immediate} \\ \text{cost}}} + \underbrace{\min_{v \in A(j)} Q_m(j,v)}_{\substack{\text{Minimum Q-value} \\ \text{for next state}}} \right) $$

    This update rule directly implements the Q-Bellman equation (4) in an iterative manner.

  3. Repeat step 2 until convergence, i.e., until the maximum change in any Q-value is below a specified threshold:

    $$ \underbrace{\max_{i \in S, u \in A(i)} |Q_{m+1}(i,u) - Q_m(i,u)|}_{\substack{\text{Maximum change in Q-values} \\ \text{between iterations}}} < \underbrace{\epsilon}_{\substack{\text{Convergence} \\ \text{threshold}}} $$

It can be mathematically proven that this iterative process converges to the optimal Q-function:

$$ \underbrace{\lim_{m \to \infty} Q_m(i,u) = Q^*(i,u)}_{\substack{\text{Convergence to optimal Q-values} \\ \text{as number of iterations approaches infinity}}} \quad \forall i \in S, u \in A(i) $$

The convergence is guaranteed under the following conditions:

  • The state and action spaces are finite
  • Every state-action pair is visited infinitely often
  • The learning rate (if used in stochastic updates) satisfies the Robbins-Monro conditions

Once the Q-function has converged, the optimal policy can be extracted by selecting the action with the minimum Q-value in each state:

$$ \underbrace{\mu^*(i) = \arg\min_{u \in A(i)} Q^*(i,u)}_{\substack{\text{Optimal policy derived} \\ \text{from optimal Q-values}}} $$

The problem

However in model-free reinforcement learning, we do not have access to the transition probabilities or reward functions. Therefore, we need to estimate the Q-function from experience.

The Q-Learning Algorithm

The Q-Learning update rule is:

$$ \underbrace{Q_{m+1}(i,u)}_{\substack{\text{Updated Q-value} \\ \text{at iteration } m+1}} = \underbrace{Q_m(i,u)}_{\substack{\text{Current Q-value} \\ \text{estimate}}} + \underbrace{\gamma_m}_{\substack{\text{Learning} \\ \text{rate}}} \left( \underbrace{g(i,u,j)}_{\substack{\text{Observed} \\ \text{immediate cost}}} + \underbrace{\min_{v \in A(j)} Q_m(j,v)}_{\substack{\text{Estimated minimum Q-value} \\ \text{for next state}}} - \underbrace{Q_m(i,u)}_{\substack{\text{Current Q-value} \\ \text{estimate}}} \right) $$

where:

  • $Q_m(i,u)$ is the current Q-value estimate for state $i$ and action $u$
  • $\gamma_m$ is the learning rate such that $\sum_{m=1}^{\infty} \gamma_m = \infty$ and $\sum_{m=1}^{\infty} \gamma_m^2 < \infty$
  • $g(i,u,j)$ is the observed immediate cost when taking action $u$ in state $i$ and transitioning to state $j$
  • $\min_{v \in A(j)} Q_m(j,v)$ is the estimated minimum Q-value for the next state $j$

This update is performed for all state-action pairs $(i,u)$ that are visited during learning.

Learning Rate Requirements

The learning rate $\gamma_m$ should be selected to satisfy the Robbins-Monro conditions:

$$ \underbrace{\sum_{m=1}^{\infty} \gamma_m = \infty}_{\substack{\text{Learning rates should} \\ \text{sum to infinity}}} \quad \text{and} \quad \underbrace{\sum_{m=1}^{\infty} \gamma_m^2 < \infty}_{\substack{\text{Sum of squared learning} \\ \text{rates should be finite}}} $$

These conditions ensure that:

  1. The learning process can overcome any initial estimation errors (first condition)
  2. The estimates eventually converge and don’t oscillate indefinitely (second condition)

Common choices for the learning rate include:

  • $\gamma_m = \frac{1}{1+\text{visits}(i,u)}$ where visits$(i,u)$ counts how many times the state-action pair has been visited
  • $\gamma_m = \frac{c}{c+m}$ where $c$ is a constant and $m$ is the iteration number

Online setting for Q-learning

In the online setting for Q-learning, we update the Q-values as we interact with the environment in real-time. The process works as follows:

Suppose state $s_t$ is visited at time $t$. The online Q-learning update rule is:

$$ \underbrace{Q_{t+1}(s_t,a_t)}_{\substack{\text{Updated Q-value} \\ \text{at time } t+1}} = \underbrace{Q_t(s_t,a_t)}_{\substack{\text{Current Q-value}}} + \underbrace{\gamma_t(s_t,a_t)}_{\substack{\text{Learning rate}}} \left( \underbrace{g(s_t,a_t,s_{t+1})}_{\substack{\text{Observed} \\ \text{immediate cost}}} + \underbrace{\min_{u \in A(s_{t+1})} Q_t(s_{t+1},u)}_{\substack{\text{Estimated minimum Q-value} \\ \text{for next state}}} - \underbrace{Q_t(s_t,a_t)}_{\substack{\text{Current Q-value}}} \right) $$

with:

$$ Q_{t+1}(s,a) = Q_t(s,a) \quad \forall s \neq s_t \text{ or } a \neq a_t $$

Exploration-Exploitation Tradeoff and ε-greedy policy

When we are at state $s_t$, which action should we take?

We cannot just take the action with minimum Q-value - we have to do exploration. A common approach is:

  • We select $a_t$ randomly from the set $A(s_t)$ with some exploration probability
  • Then update the value of Q-value for the state-action pair

An alternative way of rewriting the Q-learning update is:

$$ \underbrace{Q_{t+1}(s_t,a_t)}_{\substack{\text{Updated Q-value} \\ \text{at time } t+1}} = \underbrace{Q_t(s_t,a_t)}_{\substack{\text{Current Q-value}}} + \underbrace{\gamma_t(s_t,a_t)}_{\substack{\text{Learning rate}}} \left( \underbrace{g(s_t,a_t,s_{t+1})}_{\substack{\text{Observed} \\ \text{immediate cost}}} + \underbrace{Q_t(s_{t+1},a_{t+1})}_{\substack{\text{Q-value for} \\ \text{next state-action}}} - \underbrace{Q_t(s_t,a_t)}_{\substack{\text{Current Q-value}}} \right) $$

For action selection, a common strategy is the ε-greedy approach:

$$ a_t = \begin{cases} \underbrace{\arg\min_{u \in A(s_t)} Q_t(s_t,u)}_{\substack{\text{Exploitation:} \\ \text{Choose best action}}} & \text{with probability } 1-\varepsilon \\ \underbrace{\text{random action from } A(s_t)}_{\substack{\text{Exploration:} \\ \text{Try new actions}}} & \text{with probability } \varepsilon \end{cases} $$

For the next state, we typically choose:

$$ a_{t+1} = \underbrace{\arg\min_{u \in A(s_{t+1})} Q_t(s_{t+1},u)}_{\substack{\text{Best action according} \\ \text{to current Q-values}}} $$

This exploration-exploitation tradeoff is crucial for effective Q-learning.

SARSA: On-Policy TD Control

SARSA (State-Action-Reward-State-Action) is an on-policy temporal difference control algorithm for reinforcement learning. Unlike Q-learning, which is an off-policy method, SARSA learns the Q-values based on the actions actually taken by the current policy.

Algorithm Overview

The name “SARSA” comes from the quintuple $(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})$ that makes up the core of the algorithm. The key difference from Q-learning is that SARSA uses the actual next action $a_{t+1}$ that is chosen according to the current policy, rather than the theoretical best action.

SARSA Update Rule

The update rule for SARSA is:

$$ \underbrace{Q_{t+1}(s_t,a_t)}_{\substack{\text{Updated Q-value} \\ \text{at time } t+1}} = \underbrace{Q_t(s_t,a_t)}_{\substack{\text{Current Q-value}}} + \underbrace{\gamma_t(s_t,a_t)}_{\substack{\text{Learning rate}}} \left( \underbrace{g(s_t,a_t,s_{t+1})}_{\substack{\text{Observed} \\ \text{immediate cost}}} + \underbrace{Q_t(s_{t+1},a_{t+1})}_{\substack{\text{Q-value for actual} \\ \text{next state-action pair}}} - \underbrace{Q_t(s_t,a_t)}_{\substack{\text{Current Q-value}}} \right) $$

Action Selection in SARSA

For SARSA, both the current action $a_t$ and the next action $a_{t+1}$ are selected using the same policy, typically ε-greedy:

$$ a_t = \begin{cases} \underbrace{\arg\min_{u \in A(s_t)} Q_t(s_t,u)}_{\substack{\text{Exploitation:} \\ \text{Choose best action}}} & \text{with probability } 1-\varepsilon \\ \underbrace{\text{random action from } A(s_t)}_{\substack{\text{Exploration:} \\ \text{Try new actions}}} & \text{with probability } \varepsilon \end{cases} $$

Similarly for the next action:

$$ a_{t+1} = \begin{cases} \underbrace{\arg\min_{u \in A(s_{t+1})} Q_t(s_{t+1},u)}_{\substack{\text{Exploitation:} \\ \text{Choose best action}}} & \text{with probability } 1-\varepsilon \\ \underbrace{\text{random action from } A(s_{t+1})}_{\substack{\text{Exploration:} \\ \text{Try new actions}}} & \text{with probability } \varepsilon \end{cases} $$

SARSA as an On-Policy Algorithm

SARSA is considered an on-policy algorithm because it learns Q-values based on the actual behavior of the policy being followed, including its exploratory moves. This makes SARSA more conservative than Q-learning in some scenarios, as it takes into account the risk associated with exploration.

Extensions of SARSA

There are several extensions to the basic SARSA algorithm:

  • Double SARSA: Similar to Double Q-learning, it maintains two sets of Q-values to reduce overestimation bias
  • Expected SARSA: Instead of using the Q-value of the actual next action, it uses the expected Q-value under the current policy
  • n-step SARSA: Extends the update to consider n steps ahead rather than just the immediate next step