In RL, we have an agent that lives in a universe with some reward function that guides how the agent should act. Our goal is for the agent to learn policies ("how to act") that maximize reward gained in this universe.

MDPs

Usually, we model the universe the agent lives in as a Markov Decision Process (MDP).

• An episodic¹ MDP is defined by a tuple $\mathcal{M} = (S, A, H, T, r)$
  • State space $S$: the representation of the environment
  • Action space $A$: the actions the agent can take
  • Horizon $H$: the number of time-steps in an "episode"²
  • Transition kernel $T$: the "physics engine" of the universe, mapping a state-action pair to a probability distribution over the next state: $$T: S \times A \rightarrow \Delta(S)$$
  • Reward function $r$: the scalar feedback signal $r_h(s_h, a_h)$ received at step $h$

The goal of RL is to find a policy $\pi: S \rightarrow \Delta(A)$ that maximizes the expected cumulative reward.

Q-function and value functions

How do we evaluate how "good" a policy is? We define value functions.

Value function $V^\pi(s)$

The value function represents the expected cumulative reward if the agent starts in state $s$ and strictly follows policy $\pi$ until the end of the horizon: $$V_h^\pi(s) = \mathbb{E}\left[\sum_{t=h}^H r_t(s_t, a_t) \mid s_h = s, \pi\right]$$ This expectation is over two independent sources of randomness - i.e. $\mathbb{E}_{s_t, a_t \sim (T, \pi)} = \mathbb{E}_{s_t} \mathbb{E}_{a_t \sim \pi(\cdot \mid s_t)}$

1. the policy may be stochastic: $a_t \sim \pi_t(\cdot \mid s_t)$
2. the environment is stochastic: $s_{t+1} \sim T(\cdot \mid s_t, a_t)$

Q-function $Q^\pi(s,a)$

The Q-function (aka. action-value function) represents the expected cumulative reward if the agent starts in state $s$, takes a specific action $a$, and then follows policy $\pi$ afterward: $$Q_h^\pi(s,a) = r_h(s,a) + \mathbb{E}_{s' \sim T(\cdot \mid s, a)}[V^\pi_{h+1}(s')]$$^ in word: "the best value you can get from taking action $a$ in state $s$ equals the reward you can collect right now, plus (averaged over wherever the environment might send you next) the best value obtainable from the next state if you keep acting optimally."

• $\max_{a'}$ := "act optimally from here onward"
• $\mathbb{E}_{s'}$ := accounting for the environment's stochastic response to your action

The core idea here is the recursion - optimal long-run value splits cleanly into reward now + optimal value of the future.

Optimal Q-function $Q^*$

The goal of RL is to find the optimal policy $\pi^*$, which corresponds to the optimal Q-function $Q^*$. If we know $Q^*(s,a)$ perfectly, we effectively have the optimal policy $\pi^*$:

• 🔑 In any state $s$, pick the action $a$ that maximizes $Q^*$
• 💡 The optimal Q-function satisfies the Bellman Optimality Equation: $$Q^*_h(s,a) = r_h(s,a) + \mathbb{E}_{s' \sim T(\cdot \mid s,a)} \left[\max_{a'} Q^*_{h+1} (s', a')\right]$$

Model-free RL

Model-free RL encompasses methods that find the optimal policy $\pi^*$ but skip "learning the model - i.e. skips learning the transition kernel $T$ or the reward function $r$. The agent doesn't try to understand the physics of the world; it just tries to learn the $Q^*$ function directly through trial and error.

Q-learning

Q-learning is one of the foundational model-free RL algorithms! It uses the Bellman equation as an update rule.

• When the agent experiences a transition $(s, a, r, s')$, it updates its estimate of $Q(s,a)$ by nudging it toward a "target": $$Q(s,a) \leftarrow Q(s,a) + \alpha \left(r + \gamma \max_{a'} Q(s', a') - Q(s,a)\right)$$where $\alpha$ is the learning rate and $\gamma$ is a discount factor.
  • $\alpha \in (0, 1]$: how far you move toward the new estimate on each update
  • $\gamma \in [0, 1]$: how much you care about future reward vs. immediate; a reward $k$ steps away is worth $\gamma^k$ of its face value.
• 💡 Intuition for the update: We can split the update into two pieces: $$Q(s,a) \leftarrow Q(s,a) + \alpha \left[\underbrace{r + \gamma \max_{a'} Q(s', a')}_\text{target} - \underbrace{Q(s,a)}_\text{current guess}\right]$$
  • The bracket is the TD error: the gap between what you currently believe $Q(s,a)$ is, and a freshly informed estimate (the target) built from the reward you actually just received plus your current best guess of the future ($\max_{a'} Q(s', a')$, i.e. the discounted reward you expect to receive in the future, given that you act optimally based on your current estimate of $Q$).
  • 🔑 Connection to the Bellman optimality equation: Notice that the target $r + \gamma \max_{a'} Q(s', a')$ is precisely the RHS of the Bellman optimality equation ($r_h(s,a) + \mathbb{E}_{s' \sim T(\cdot \mid s,a)} \left[\max_{a'} Q^*_{h+1} (s', a')\right]$), except without the expectation over $s'$ because this expectation is not computable without knowing $T$ - so we substitute the single $s'$ we happened to land in as one sample of it.
    • 💡 ^ The idea is that if we repeatedly do these updates over enough data points $(s, a, r, s')$, nudging our tabular $Q(s,a)$ a bit each time, we will have approximated the expectation over $s'$ using these iterative updates s.t. $Q \rightarrow Q^*$.
    • 🔖 The convergence guarantee: Tabular Q-learning converges to $Q^*$ with probability 1, provided the following conditions hold:
      • Every $(s,a)$ pair is visited infinitely often.
      • The learning rate decays correctly: $\sum_t \alpha_t = \infty$ but $\sum_t \alpha_t^2 < \infty$ → the steps must be large enough in total to travel any distance, but shrink fast enough to stop the noise from perpetually jostling the estimate.
      • Bounded rewards, and $\gamma < 1$ (or a proper finite horizon).
      • 🔑 ^ under these conditions, the nudging provably drives $Q \rightarrow Q^*$. The mechanism for this proof is a fixed-point argument: the Bellman optimality operator $\mathcal{T}$ is a contraction in the max-norm with factor $\gamma$, so repeatedly applying it pulls any starting estimate toward its unique fixed point $Q^*$. Q-learning is a stochastic, sampled version of iterating that contraction: each update applies $\mathcal{T}$ approximately, using one sampled $s'$ in place of the true expectation, and the decaying step size averages out the sampling noise so the approximate iteration still lands on the same fixed point.
• ❓ Is Q-learning neural-network based? No, original Q-learning is tabular - you keep a lookup table with one cell per $(s,a)$ pair and edit cells directly using the update rule above.

Model-based RL

Model-based RL explicitly learns the rules of the universe. Using collected data, we aim to approximate the transition kernel $\hat{T}(s' \mid s,a)$ and the reward $\hat{r}(s,a)$ (as well as potentially other relevant information about the universe). Once we have this simulated "world model," a planner can be used to search through possible action sequences to find the one that yields the highest return.

• Model-based methods originally started out fully tabular - e.g. for small discrete MDPs, we can just count what we see.
  • Estimate $\hat{T}(s' \mid s,a)$ by the empirical frequency of landing in $s'$ after taking $a$ in $s$
  • Estimate $\hat{r}(s,a)$ by averaging the rewards you saw
  • 🔖 Obtain a policy using these estimated values ^ + value iteration / policy iteration.
• Modern versions of model-based RL have explored more complex ways of modeling $\hat{T}$ and $\hat{r}$, e.g. -
  • Gaussian processes, linear models, Gaussian mixtures
  • Neural networks
  • 💡 These formulations of $\hat{T}$ and $\hat{r}$ make it possible to scale the "rules of the universe" to apply to large, continuous worlds - i.e. the tabular method fails when $S$ is continuous.

Once we have a fully specified MDP (that we learned via model-based RL), we can compute the optimal policy from it using methods such as value iteration (VI) and policy iteration (PI). These are essentially the planning engines that model-based RL plugs into.

Footnotes

1. Alternative would be continuous, i.e. infinite horizon. ↩

2. One "lifetime" in this universe. ↩