Cheat sheet

Reinforcement learning

10 formulas · Back to the formula library

  1. Action-value function

    Qπ(s,a)=Eπ ⁣[Gt∣St=s,At=a]Q^{\pi}(s, a) = \mathbb{E}_{\pi}\!\left[G_t \mid S_t = s, A_t = a\right]

    How good one action is in one state, assuming you behave normally afterwards. Unlike the state value it names a choice, so a greedy policy can be read straight off it without a model of the environment.

    Symbols

    QπQ^{\pi}
    The action-value function under policy pi.
    aa
    The action taken in state s.
  2. Advantage function

    Aπ(s,a)=Qπ(s,a)−Vπ(s)A^{\pi}(s, a) = Q^{\pi}(s, a) - V^{\pi}(s)

    How much better one action is than the state's average. Subtracting the state value removes everything the choice had no say in, which cuts gradient variance without biasing the estimate.

    Symbols

    AπA^{\pi}
    The advantage of action a in state s.
    QπQ^{\pi}
    The value of that specific action.
    VπV^{\pi}
    The average value of the state.
  3. Bellman expectation equation

    Vπ(s)=Eπ ⁣[r+γVπ(s′)∣s]V^{\pi}(s) = \mathbb{E}_{\pi}\!\left[r + \gamma V^{\pi}(s') \mid s\right]

    Value defined in terms of itself one step later: a reward now, plus the discounted value of wherever you land. Every value-based algorithm is some way of solving this fixed point.

    Symbols

    s′s'
    The next state.
    rr
    The immediate reward.
    γ\gamma
    The discount factor.
  4. Bellman optimality equation

    V∗(s)=max⁡aE ⁣[r+γV∗(s′)∣s,a]V^{*}(s) = \max_{a} \mathbb{E}\!\left[r + \gamma V^{*}(s') \mid s, a\right]

    The same recursion with a maximum where the policy used to be. It describes the best achievable value without reference to any particular policy, and the greedy choice over it is an optimal policy.

    Symbols

    V∗V^{*}
    The optimal value function.
    max⁡a\max_{a}
    Taking the best available action rather than the usual one.
  5. Discounted return

    Gt=∑k=0∞γkrt+k+1G_t = \sum_{k=0}^{\infty} \gamma^{k} r_{t+k+1}

    The total future reward from a point onwards, with later rewards worth less. The discount both encodes impatience and keeps the sum finite on tasks that never end.

    Symbols

    GtG_t
    The return from time t onwards.
    γ\gamma
    The discount factor, between zero and one.
    rr
    The reward collected at a single step.
  6. PPO clipped objective

    L=E ⁣[min⁡ ⁣(ρtAt,  clip(ρt,1−ϵ,1+ϵ)At)]L = \mathbb{E}\!\left[\min\!\left(\rho_t A_t, \; \mathrm{clip}(\rho_t, 1-\epsilon, 1+\epsilon) A_t\right)\right]

    Limits how far one update may move the policy by clipping the probability ratio and taking the pessimistic branch. That single trick is why PPO trains stably enough to be the workhorse of RLHF.

    Symbols

    ρt\rho_t
    The ratio of new to old action probability.
    AtA_t
    The advantage estimate for that step.
    ϵ\epsilon
    The clip width, typically 0.2.
  7. Q-learning update

    Q(s,a)←Q(s,a)+α ⁣[r+γmax⁡a′Q(s′,a′)−Q(s,a)]Q(s, a) \leftarrow Q(s, a) + \alpha\!\left[r + \gamma \max_{a'} Q(s', a') - Q(s, a)\right]

    Nudges the value of the action you took toward the reward plus the best value available next. The max is over actions you did not necessarily take, which is what makes it off-policy and lets it learn the optimal policy while exploring.

    Symbols

    α\alpha
    The learning rate.
    max⁡a′Q(s′,a′)\max_{a'} Q(s', a')
    The best value available in the next state.
    rr
    The reward just received.
  8. REINFORCE policy gradient

    ∇θJ=Eπθ ⁣[∇θlog⁡πθ(a∣s) Gt]\nabla_{\theta} J = \mathbb{E}_{\pi_\theta}\!\left[\nabla_{\theta} \log \pi_{\theta}(a \mid s)\, G_t\right]

    Raises the log-probability of actions that led to high return and lowers it for the rest. It optimises the policy directly with no value model required, and its variance is high enough that a baseline is essentially mandatory.

    Symbols

    JJ
    The expected return being maximised.
    πθ\pi_{\theta}
    The policy, parameterised by theta.
    GtG_t
    The return that followed the action.
  9. State-value function

    Vπ(s)=Eπ ⁣[Gt∣St=s]V^{\pi}(s) = \mathbb{E}_{\pi}\!\left[G_t \mid S_t = s\right]

    How good a state is: the return you expect from it if you keep following your current policy. It judges the situation, not the choice — which is why it cannot on its own tell you what to do.

    Symbols

    VπV^{\pi}
    The value function under policy pi.
    ss
    The state being evaluated.
    π\pi
    The policy whose behaviour is being assumed.
  10. Temporal-difference error

    δt=rt+1+γV(st+1)−V(st)\delta_t = r_{t+1} + \gamma V(s_{t+1}) - V(s_t)

    The gap between what you predicted and what the next step plus the next prediction say. It is the learning signal for every TD method, and it lets you learn from a single transition without waiting for the episode to end.

    Symbols

    δt\delta_t
    The error at step t.
    V(st)V(s_t)
    The current prediction.
    rt+1+γV(st+1)r_{t+1} + \gamma V(s_{t+1})
    The one-step bootstrapped target.
Esc
↑↓ navigate↵ open? shortcuts

Keyboard shortcuts

Press Esc to close

Anywhere

⌘K
Search and commands
/
Search
?
This sheet
Esc
Close

Reading a lesson

J
Next lesson
K
Previous lesson
B
Bookmark