Reinforcement / Foundations
verifiedBellman Equation
The value of where you are is the reward you get now plus the value of where you end up. Written down, that sentence is the whole of dynamic programming and the thing every method in this domain is approximating — it turns a question about an infinite future into a relationship between adjacent moments.
Every algorithm here is a way of making it hold approximately when it cannot be solved exactly. Value iteration applies it as an update until the values stop moving. Temporal-difference learning applies it to sampled transitions rather than to a known model. Q-learning applies it with a maximum over actions, which is what makes it off-policy. The differences between them are differences in what is sampled and what is assumed, over one equation.
V(s) = E[r + γV(s′)] — the value of a state is the expected immediate reward plus the discounted value of the next. The discount γ is doing more than taste: below one it makes an infinite sum finite and makes the update a contraction, so repeated application converges to a unique fixed point. At γ = 1 that guarantee is gone, which is why episodic tasks need a terminal state and why a discount near one is where instability starts.
discounted-tail holds 29% of the budget; rest holds the remaining 71%.
Value the discount assigns to the far future, against the value of the next few steps, in equal units. Drag the discounted tail up to watch the horizon lengthen — at the far right the contraction weakens, which is where the guarantee that this converges runs out.
Reviewed by opendroid · 2026-08-18
- arXiv:1312.5602 — Playing Atari with Deep Reinforcement Learning
- arXiv:1506.02438 — High-Dimensional Continuous Control Using Generalized Advantage Estimation
Origin · not linkable
- Bellman 1957 — Dynamic Programming · Princeton University Press · doi:10.1515/9781400835386