Reinforcement Learning: Teaching Agents to Make Decisions

A driver who is never told the right answer

An Ola or Uber driver in Bengaluru finishes a drop near Indiranagar at 6:40 pm. She has to decide, right now, where to drive next: sit at the drop point, head toward the Domlur tech-park exit rush, or cross town toward the airport road. Nobody hands her a labelled dataset of "correct" decisions. She does not get told "the right choice was Domlur" the moment she picks a spot. What she gets, twenty or thirty minutes later, is a number — the fare of the next ride she is offered, or zero if nothing comes. Over months of shifts she builds an intuition: Domlur at 6:40 pm tends to pay off; the airport road at that hour is usually dead. Nobody programmed that intuition into her. She learned it by acting, waiting, and updating her sense of which choices lead to good outcomes later, using only the rewards she actually received.

This is the exact problem reinforcement learning (RL) formalizes: an agent that must choose actions inside an environment it does not fully know in advance, receiving only a scalar reward after each action, with the ultimate goal being not the biggest single reward but the biggest total reward accumulated over a whole sequence of decisions. It is a fundamentally different learning problem from the supervised learning and neural-network training you have already studied, and the difference is worth being precise about before writing a single equation.

Why this is not supervised learning wearing a costume

In supervised learning, every training example arrives as a pair: an input and the correct output for that input. A spam classifier is shown an email and told "spam" or "not spam" directly. The loss function compares the prediction to that known correct answer on every single example.

Reinforcement learning has no such labels anywhere in the loop. The driver is never told "you should have chosen Domlur." She is only told, after the fact, how much a ride paid. Three problems fall out of this immediately, and each one has a name:

• No supervision signal per action. The agent must discover good actions through consequences, not imitation of labelled examples.
• Delayed and sparse feedback. A reward observed now might be the consequence of a decision made several steps earlier — driving toward Domlur was the useful decision, but the payoff only arrived after the wait. This is called the credit assignment problem: figuring out which of several past actions actually deserves credit for a later reward.
• The agent's own choices generate its training data. Unlike a fixed dataset, the sequence of states an RL agent sees depends on the actions it took, which depends on what it has learned so far. Change the policy and you change the very data used to improve the policy.

Keep this hook running as we build the formal machinery — every symbol introduced below is answering a specific piece of the driver's problem: what does she observe, what can she do, what is the environment's response, and how does she turn a stream of rewards into a decision rule.

The formal skeleton: Markov Decision Processes

RL problems are almost always modelled as a Markov Decision Process (MDP), defined by a tuple (S, A, P, R, γ):

• S, the set of states — everything the agent can observe about the situation right now. For the driver: her location, the time of day, maybe the day of the week.
• A, the set of actions available in each state — which zone to drive toward next.
• P(s' | s, a), the transition dynamics — the probability of landing in state s' given the agent was in state s and took action a. In Bengaluru traffic this is genuinely random; in the toy example below we will make it deterministic so every number can be checked by hand.
• R(s, a, s'), the reward function — the scalar payoff for that particular transition. The fare earned, or the −1 "cost" of a wasted minute idling.
• γ (gamma), the discount factor, a number between 0 and 1 that shrinks the value of rewards the further into the future they lie.

The word "Markov" carries a specific, load-bearing assumption: the next state and reward depend only on the current state and action, not on the entire history that led there. The driver's decision at 6:40 pm should in principle only need to know she is at Indiranagar at 6:40 pm — not the exact sequence of rides she took all afternoon. This assumption is what makes the mathematics tractable, and it is also the first place real systems cheat: a genuinely Markov state for a delivery-routing agent would need to fold traffic history, weather, and event calendars into the state representation itself, since the raw GPS coordinate alone is not really Markov for predicting the next reward.

The discount factor γ is not a cosmetic detail. It encodes how much the agent should prefer a reward now over an equally-sized reward later, and — critically for infinite or long-running tasks — it keeps the total reward from summing to infinity. The quantity the agent is actually trying to maximize is the return:

G_t = r_{t+1} + γ·r_{t+2} + γ²·r_{t+3} + γ³·r_{t+4} + ...

Concretely: if the agent will earn rewards of 10, 10, 10, 10 on four consecutive future steps, the undiscounted sum (γ = 1) is 40. With γ = 0.9 the return is 10 + 9 + 8.1 + 7.29 = 34.39 — noticeably less, because later rewards count for less. This is exactly why an agent trained with γ = 0.9 will happily take a small loss now to reach a bigger reward two steps away, but will not chase a huge reward that is fifty steps away nearly as eagerly as one that is two steps away — the far-away reward gets multiplied by γ raised to a large power and shrinks toward zero.

Value functions and the Bellman equation

Two functions summarize "how good" a situation is, both defined as expected return from here onward, assuming the agent behaves optimally afterward:

• V*(s), the optimal state-value function — the best possible expected return starting from state s.
• Q*(s, a), the optimal action-value function — the best possible expected return starting from state s, taking action a right now, and behaving optimally after that.

These satisfy the Bellman optimality equation, which is really just "the return of the best action now equals its immediate reward plus the discounted value of the best action after that":

Q*(s, a) = Σ_s' P(s'|s,a) · [ R(s,a,s') + γ · max_a' Q*(s', a') ]

For a deterministic environment (one action leads to exactly one next state, our toy example below), the sum over s' disappears and this collapses to:

Q*(s, a) = R(s,a,s') + γ · max_a' Q*(s', a')

This equation is a fixed-point condition, not a formula you evaluate once — Q* appears on both sides. Q-learning is the algorithm that finds this fixed point by repeated trial and error, without ever needing to know P or R in advance. The agent maintains a table of current estimates Q(s, a), starts them all at zero (total ignorance), and after every real transition it observes — state s, action a, reward r, next state s' — it nudges its estimate toward what the Bellman equation says it should be:

Q(s, a) ← Q(s, a) + α · [ r + γ · max_a' Q(s', a') − Q(s, a) ]

Here α (alpha) is the learning rate, between 0 and 1, controlling how big a step is taken toward the new evidence. The bracketed term r + γ·max_a' Q(s',a') − Q(s,a) is called the temporal-difference (TD) error — the gap between what the agent currently believes and what the one new piece of experience suggests it should believe.

Worked example: three episodes on a three-state track

The driver's real problem has too many states and too much randomness to trace by hand. Strip it down to its skeleton: three states {0, 1, 2} arranged on a line, with state 2 the goal (a zone with a guaranteed high-value ride). Two actions are available everywhere: R (move one state right, toward the goal) and L (move one state left, or stay at 0 if already there). Every non-goal step costs −1 reward (fuel and time spent idling); reaching state 2 pays +10 and ends the episode. Set the discount factor γ = 0.9 and the learning rate α = 0.5. Every Q(s, a) starts at 0.

Trace three episodes in which the agent happens to pick action R at every step (we fix the action choice here purely so the arithmetic is fully deterministic and checkable; a real agent would use the exploration rule discussed in the next section instead of always picking R).

Episode 1, starting at state 0.

Step 1: state 0, action R → next state 1, reward −1 (not the goal). Update:

Q(0,R) ← 0 + 0.5·[ −1 + 0.9·max(Q(1,L), Q(1,R)) − 0 ]
       = 0 + 0.5·[ −1 + 0.9·0 − 0 ]
       = −0.5

Step 2: state 1, action R → next state 2 (goal), reward +10, episode ends, so the "next state" contributes 0:

Q(1,R) ← 0 + 0.5·[ 10 + 0.9·0 − 0 ] = 5.0

Episode 2, starting again at state 0. Q(1,R) is no longer 0, so this episode's update at state 0 is pulled higher:

Q(0,R) ← −0.5 + 0.5·[ −1 + 0.9·max(0, 5.0) − (−0.5) ]
        = −0.5 + 0.5·[ −1 + 4.5 + 0.5 ] = −0.5 + 0.5·4 = 1.5
Q(1,R) ← 5.0 + 0.5·[ 10 + 0.9·0 − 5.0 ] = 5.0 + 2.5 = 7.5

Episode 3, starting at state 0.

Q(0,R) ← 1.5 + 0.5·[ −1 + 0.9·max(0, 7.5) − 1.5 ]
        = 1.5 + 0.5·[ −1 + 6.75 − 1.5 ] = 1.5 + 0.5·4.25 = 3.625
Q(1,R) ← 7.5 + 0.5·[ 10 + 0.9·0 − 7.5 ] = 7.5 + 1.25 = 8.75

Two estimates, three episodes each: Q(0,R) moves −0.5 → 1.5 → 3.625, and Q(1,R) moves 5.0 → 7.5 → 8.75. Both are climbing, and by design they are climbing toward the true optimal values, which can be checked directly from the Bellman equation rather than just asserted. Since action R is optimal in this environment, Q*(1,R) = 10 + 0.9·0 = 10 (goal reward, nothing after). Then Q*(0,R) = −1 + 0.9·max(Q*(1,L), Q*(1,R)). Working out Q*(1,L) too: action L from state 1 returns to state 0, reward −1, so Q*(1,L) = −1 + 0.9·Q*(0,R). And Q*(0,L): action L from state 0 stays at state 0 (there is nowhere further left), so Q*(0,L) = −1 + 0.9·max(Q*(0,L), Q*(0,R)). Guessing that R dominates everywhere and solving: Q*(0,R) = −1 + 0.9·10 = 8, then Q*(1,L) = −1 + 0.9·8 = 6.2 and Q*(0,L) = −1 + 0.9·8 = 6.2. Every one of these four equations checks out with R strictly larger than L at both states, confirming the guess was consistent. So the table is converging: Q(0,R) is heading toward 8, and it moved 3.625 of the way there in three episodes (from 0); Q(1,R) is heading toward 10, and it reached 8.75 — 87.5% of the way — in the same three episodes. This is Q-learning working exactly as designed: no transition model, no reward function was ever given to the algorithm directly, only the raw (s, a, r, s') tuples it experienced.

Here is the same trace as runnable code, so the arithmetic above is not just a hand-worked claim but something you can execute and check line for line:

def step(state, action):
    if action == 'R':
        next_state = min(state + 1, 2)
    else:
        next_state = max(state - 1, 0)
    reward = 10 if next_state == 2 else -1
    done = (next_state == 2)
    return next_state, reward, done

Q = {(s, a): 0.0 for s in [0, 1, 2] for a in ['L', 'R']}
alpha, gamma = 0.5, 0.9

def q_update(s, a, r, s_next, done):
    max_next = 0.0 if done else max(Q[(s_next, 'L')], Q[(s_next, 'R')])
    Q[(s, a)] += alpha * (r + gamma * max_next - Q[(s, a)])

for episode in range(3):
    s = 0
    while s != 2:
        a = 'R'                       # forced choice, for a fully traceable example
        s_next, r, done = step(s, a)
        q_update(s, a, r, s_next, done)
        s = s_next
    print(round(Q[(0, 'R')], 4), round(Q[(1, 'R')], 4))

# Output:
# -0.5 5.0
# 1.5 7.5
# 3.625 8.75

The step function and the update rule are the only pieces of "environment knowledge" in this code, and note carefully: the agent's Q table never reads step's internals. It only ever sees the four values (s, a, r, s_next) that step hands back — exactly the restriction a real RL agent operates under, where the true dynamics of Bengaluru traffic are never available to be inspected, only sampled by acting.

The agent-environment loop, drawn out

Every RL algorithm, however sophisticated, runs the same four-arrow loop below at every single timestep. The Q-learning update in the worked example above is what happens the instant the "reward + next state" arrow arrives back at the agent.

Explore, or exploit what you already know?

In the worked example the agent always chose R, but that choice was rigged for the arithmetic to come out clean — a real learner does not know in advance that R is the good action. If it always exploited its current best guess (always picking whichever action has the higher Q-value right now), it could get permanently stuck: imagine random initial noise had made Q(0,L) look slightly larger than Q(0,R) after the very first update, purely by chance. A purely greedy agent would then keep choosing L forever and would never generate the experience needed to correct that mistake, because it never tries R again to find out it was wrong.

The standard fix is ε-greedy exploration: with a small probability ε (say 0.1), take a uniformly random action instead of the current best guess; with probability 1 − ε, exploit — take the action with the highest current Q-value. Early in training ε is often kept relatively high, since the Q-table is mostly wrong and exploration is cheap information; it is typically decayed toward a small value as training progresses and the estimates become trustworthy. This is the driver again: a driver who only ever returns to the one zone that paid well last week will never discover that a new mall opening in a different zone now pays better — she has to occasionally take a chance on an unfamiliar spot to find out.

The misconception to retire

The single most common misunderstanding at this point is treating reinforcement learning as supervised learning with a different name — imagining that somewhere in the process the agent is shown a table of "state → correct action" pairs and trained to match it, the way a classifier is trained to match image labels. It is not. At no point does anything tell the Q-learning agent above that action R was "correct" at state 0. All it ever received was the number −1 (or +10) after the fact, for a transition it had already taken, and it had to work backward through the Bellman equation, one update at a time, to figure out that state-0-then-action-R was the valuable choice. This is precisely the credit-assignment problem named earlier: a policy is being learned entirely from scalar consequences, never from being shown the right answer directly. If you find yourself thinking "the agent was trained on examples of good decisions," stop and ask what the label would even have been — in RL, there usually isn't one; there is only a reward.

Active recall

Attempt every question before reading the answer beneath it.

1. Write out the five components of the MDP tuple, and for each one give the corresponding piece of the Ola/Uber driver scenario from the opening section.
2. Using the Q-values from the end of Episode 3 in the worked example — Q(0,R) = 3.625, Q(0,L) = 0, Q(1,R) = 8.75, Q(1,L) = 0 — what action would a purely greedy policy choose at state 0, and at state 1?
3. Continue the worked example by hand for a fourth episode (still forcing action R at every step, α = 0.5, γ = 0.9). What are Q(0,R) and Q(1,R) after Episode 4?
4. A classmate says, "Q-learning is really just classification — the agent is trained to output the correct action for each state." Explain precisely what is wrong with this statement.
5. In the worked example, recompute the undiscounted return (γ = 1) of the two-step sequence reward −1 then reward +10, and compare it to the discounted return with γ = 0.9. What does the gap tell you about what discounting is doing?
6. Why does an agent that always exploits its current Q-table (ε = 0) risk never finding the optimal policy, even after unlimited episodes?

Answers

1. S = the driver's (zone, time-of-day) pair; A = the set of zones she could drive toward next; P(s'|s,a) = the (unknown, probabilistic) rule governing which zone-time she actually ends up in after choosing a direction, given Bengaluru traffic; R(s,a,s') = the fare she earns (or zero, or a small idling cost) for that transition; γ = how strongly she should prefer an early fare over an equally-sized fare several hours later in her shift.
2. At state 0: Q(0,R) = 3.625 > Q(0,L) = 0, so the greedy policy chooses R. At state 1: Q(1,R) = 8.75 > Q(1,L) = 0, so the greedy policy chooses R there too — matching the actually-optimal policy derived from the Bellman equation.
3. Step 1 (state 0, action R → state 1, reward −1): Q(0,R) ← 3.625 + 0.5·[−1 + 0.9·max(0, 8.75) − 3.625] = 3.625 + 0.5·[−1 + 7.875 − 3.625] = 3.625 + 0.5·3.25 = 3.625 + 1.625 = 5.25. Step 2 (state 1, action R → goal, reward +10): Q(1,R) ← 8.75 + 0.5·[10 + 0.9·0 − 8.75] = 8.75 + 0.5·1.25 = 8.75 + 0.625 = 9.375. Both values keep climbing toward their true optima of 8 and 10, with the gap shrinking each episode: Q(1,R)'s distance from 10 fell from 1.25 to exactly 0.625 — precisely halved, because α = 0.5 always closes half the remaining TD error and, being one step from a terminal state, its target never itself shifts. Q(0,R)'s distance from 8 fell from 4.375 to 2.75 — shrinking too, but less cleanly, since its own target depends on the still-moving Q(1,R).
4. It is wrong because classification requires a labelled dataset of (input, correct-output) pairs supplied before training, and no such labels exist in Q-learning. The only signal is the scalar reward received after acting, and the "correct" action at a state is never stated anywhere — it has to be inferred indirectly, over many episodes, by propagating reward information backward through the Bellman update. Q-learning is closer to trial-and-error credit assignment than to pattern matching against known answers.
5. Undiscounted (γ = 1): −1 + 10 = 9. Discounted (γ = 0.9): −1 + 0.9·10 = −1 + 9 = 8. The gap is exactly 1, which is 10·(1 − 0.9) = 1 — discounting shaved off 10% of the second reward's contribution because it arrives one step later. The further away a reward sits, the more of it discounting erases, which is why discounting encodes impatience: it makes the agent prefer reaching a reward sooner rather than later, even when the total undiscounted amount would be identical.
6. Because whichever action currently has the highest Q-value estimate is the only action the agent will ever take again, so any other action's true value can never be updated further, even if that action was actually better and only looked worse due to early random noise or an unlucky first sample. Without exploration, the agent's belief about the unchosen actions is frozen at whatever it happened to be after the last time it tried them — it has no mechanism to discover it was wrong.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where reinforcement learning: teaching agents to make decisions is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting reinforcement learning: teaching agents to make decisions to at least 3 other topics you have studied.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind reinforcement learning: teaching agents to make decisions, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.