Reinforcement learning — MDP, Bellman equation, Q-learning

1. The Markov Decision Process (MDP)

2. Policies, Returns, and Value

3. Deriving the Bellman Equation (from scratch)

Now take the expectation under policy $\pi$ : $V^\pi(s) = \mathbb{E}_\pi[R_t + \gamma G_{t+1}\mid s_t=s]$ Split expectation over the action, then over the next state: $\boxed{V^\pi(s) = \sum_a \pi(a\mid s)\sum_{s'} P(s'\mid s,a)\Big[R(s,a) + \gamma\,V^\pi(s')\Big]}$

Figure — Reinforcement learning — MDP, Bellman equation, Q-learning

4. Q-learning (solving it WITHOUT knowing $P$ )

Formula Q-learning update — derivation

The Bellman target for a single observed transition is: $\text{target} = r + \gamma\,\max_{a'} Q(s',a')$ Our current estimate is $Q(s,a)$ . The mismatch is the TD error: $\delta = \underbrace{r + \gamma\max_{a'}Q(s',a')}_{\text{target}} - \underbrace{Q(s,a)}_{\text{estimate}}$ Move a small step $\alpha$ toward the target (this is stochastic approximation / online gradient of the squared TD error): $\boxed{Q(s,a)\leftarrow Q(s,a) + \alpha\Big[r + \gamma\max_{a'}Q(s',a') - Q(s,a)\Big]}$ Why the $\max$ (not the action actually taken next)? It makes Q-learning off-policy: it learns the optimal value even while exploring with a different, exploratory policy.

5. Common Mistakes (Steel-manned)

6. Flashcards

What five elements define an MDP?

States

S

, Actions

A

, Transition

P(s'|s,a)

, Reward

R

, Discount

\gamma

What is the Markov property?

The next state depends only on the current state and action, not on earlier history.

Why do we discount future rewards with

\gamma<1

To keep infinite-horizon returns finite/convergent and to value near-term rewards more than distant ones.

State the Bellman optimality equation for

Q^*

Q^*(s,a)=\sum_{s'}P(s'|s,a)[R(s,a)+\gamma\max_{a'}Q^*(s',a')]

Write the Q-learning update rule.

Q(s,a)\leftarrow Q(s,a)+\alpha[r+\gamma\max_{a'}Q(s',a')-Q(s,a)]

What is the TD error?

\delta = r+\gamma\max_{a'}Q(s',a') - Q(s,a)

: the gap between Bellman target and current estimate.

Why is Q-learning called "model-free" and "off-policy"?

Model-free: it samples real transitions instead of using

P

. Off-policy: the

\max

target learns the optimal policy while exploring with a different (

\varepsilon

-greedy) policy.

Difference between Q-learning and SARSA in the target?

Q-learning uses

\max_{a'}Q(s',a')

; SARSA uses

Q(s',a')

for the action actually taken next.

How do you recover the optimal policy from

Q^*

\pi^*(s)=\arg\max_a Q^*(s,a)

What does

\varepsilon

-greedy balance?

Exploration (random actions) vs exploitation (greedy best-known action).

Given

\alpha=0.5,\gamma=0.9,Q=2,r=1,\max Q'=6

, new

Q

target

=1+0.9\cdot6=6.4

\delta=4.4

Q\leftarrow2+0.5\cdot4.4=4.2

Recall Feynman: explain to a 12-year-old

Imagine a video game where you don't get points immediately — sometimes the good move now only pays off ten moves later. You keep a scorebook that guesses "how many points can I eventually get if I press this button in this situation?" Every time you play, you peek at where you ended up, see how many points you could get from there, and gently fix your guess to be a little more correct. Do this thousands of times and your scorebook tells you the best button for every situation — even though nobody ever told you the rules of the game. That scorebook is $Q$ , and fixing-your-guess is Q-learning.

Connections

Markov Chains — MDP = Markov chain + actions + rewards
Dynamic Programming — Bellman equation is the DP recursion; value/policy iteration solve it when $P$ is known
Stochastic Approximation — justifies the $\alpha$ -step Q-update
Deep Q Networks (DQN) — replace the $Q$ table with a neural net for large state spaces
Optimal Control — Bellman ⟷ Hamilton–Jacobi–Bellman equation in aerospace guidance
Gradient Descent — TD update is (semi-)gradient descent on squared TD error

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, Reinforcement Learning ka core idea simple hai: ek agent (maano autopilot) kisi environment mein actions leta hai, aur turant answer nahi milta — sirf reward milta hai, kabhi late bhi. Problem yeh hai ki abhi liya gaya action future ke rewards ko affect karta hai (smooth landing tabhi hoga jab tumne kai steps pehle sahi throttle diya). Isko model karne ke liye hum MDP use karte hain: states, actions, transition probability $P$ , reward $R$ , aur discount $\gamma$ . Markov property ka matlab — future sirf current state pe depend karta hai, poori history yaad rakhne ki zaroorat nahi, bas state mein saari relevant cheezein (velocity, angle) daal do.

Bellman equation bas ek recursion hai: aaj ki value = abhi ka reward + $\gamma$ times "jahan pahuchoge uski value". Yeh peeche ki taraf value propagate karta hai — goal ka reward slowly-slowly pichhle states tak pahuchta hai, har step pe $\gamma$ se multiply hote hue. Isiliye door ka reward bhi aaj ke decision ko guide karta hai.

Q-learning ka magic yeh hai ki humein $P$ (physics model) pata hone ki zaroorat nahi. Turbulence, unknown dynamics — koi baat nahi. Bas real experience $(s,a,r,s')$ se seekho: target banao $r + \gamma \max_{a'}Q(s',a')$ , apne purane guess se compare karo (yeh gap hai TD error), aur chhota sa step $\alpha$ lo target ki taraf. Yeh baar-baar karo, aur $Q$ table batayega har situation mein best action. Exploration ke liye $\varepsilon$ -greedy use karo — kabhi-kabhi random action, warna tum apne early galat estimate mein hi phas jaoge. Aerospace mein guidance, control, aur autonomous decision-making ke liye yeh foundational hai.

Test yourself — Machine Learning (Aerospace Applications)

Connections