What is Reinforcement Learning?

This is, arguably, the most natural form of learning: it is how humans, animals, and even infants learn. A baby is not given labelled examples of “how to walk”; it tries, falls, gets feedback (pain, support from a parent, balance restored), and gradually improves.

At discrete time step $t$, the agent observes a state $S_t\in \mathcal{S}$ and selects an action $A_t\in \mathcal{A}$. The environment then produces a scalar reward $R_{t+1}\in \mathbb{R}$ and transitions to a new state $S_{t+1}$. The elementary interaction pattern is:

The objective is to learn a way of acting (a policy) that maximizes cumulative reward over time, not only the next immediate reward. Hence, reinforcement learning is not merely prediction: it is about choosing actions that actively influence future situations and future rewards.

1.1 The Three Paradigms of Learning

To appreciate RL, contrast it with the two paradigms you may already know:

In supervised learning, examples of correct behaviour are supplied by an external supervisor. In reinforcement learning, such examples are usually not available. The agent may know that an outcome was good or bad, but it may not know which action should have been chosen instead. This creates the primary need for exploration and credit assignment.

Sutton & Barto identify three characteristics as the most important distinguishing features of reinforcement learning problems:

1. Closed-loop in an essential way: The learning system's actions influence its later inputs. This creates a feedback cycle that does not exist in supervised learning, where predictions do not affect future training examples.
2. No direct instructions: The agent is not told which actions to take. Unlike supervised learning, there are no labelled examples of correct behaviour. The agent must discover which actions yield the most reward by trying them out (trial-and-error search).
3. Consequences play out over extended time periods (Delayed reward): Actions may affect not only the immediate reward but also the next situation, and through that, all subsequent rewards. In the most interesting and challenging cases, these effects unfold over many steps.

1.2 Why "Deep" Reinforcement Learning?

Classical RL is built on tables and tabular updates (we will see exactly this in the tic-tac-toe example). But for problems with huge state spaces (Atari frames, robotic joint configurations, Go boards), we cannot store one entry per state.

Deep Reinforcement Learning replaces those tables with deep neural networks that approximate value functions and/or policies. The foundations, however, remain the same as classical RL—so we will spend a lot of time on the classical ideas before bringing in deep learning.

The Agent–Environment Interface

The two fundamental entities in RL are the agent and the environment.

1.3 The Interaction Loop

At every discrete time step $t=0,1,2,\dots$ the following loop runs:

1. The agent observes the current state $S_t$.
2. The agent picks an action $A_t$.
3. The environment transitions to a new state $S_{t+1}$ and emits a scalar reward $R_{t+1}$.
4. The agent uses $(S_{t+1},R_{t+1})$ to update its internal knowledge and choose the next action.

This loop is the heart of all RL. Every algorithm we study—tabular methods, Q-learning, policy gradients, deep RL—fits inside this loop.

1.4 The Core Elements of Reinforcement Learning

1. Agent – the entity that learns.
2. Environment – everything outside the agent.
3. State $S_t$ – a description of the current situation. Could be a chess board, a sensor reading, an image.
4. Action $A_t$ – what the agent does at time $t$. May be discrete (left/right/up/down) or continuous (steering angle in $[-30^{\circ },30^{\circ }]$).
5. Reward $R_{t+1}$ – a single scalar number returned by the environment after the agent acts.

1.5 The Fourth Sub-Element: Model of the Environment

Beyond the agent and the environment, Sutton & Barto identify four main sub-elements in a reinforcement learning system:

1. Policy: Defines the learning agent's way of behaving at a given time — a mapping from perceived states to actions. It corresponds to what psychology would call a set of stimulus–response rules or associations. The policy alone is sufficient to determine behaviour; it is the core of an RL agent. In general, policies may be stochastic.
2. Reward signal: Defines the goal of the RL problem. On each time step, the environment sends a single number to the agent. The agent's sole objective is to maximize the total reward it receives over the long run. The reward signal is the primary basis for altering the policy. Reward signals may be stochastic functions of the environment state and the actions taken.
3. Value function: Specifies what is good in the long run. The value of a state is the total amount of reward an agent can expect to accumulate over the future, starting from that state. Whereas rewards are primary (given directly by the environment), values are secondary (estimated and re-estimated from sequences of observations). The most important component of almost all RL algorithms is a method for efficiently estimating values.
4. Model of the environment (optional): Something that mimics the behaviour of the environment, allowing inferences about how the environment will behave. Given a state and action, a model might predict the resultant next state and next reward.

The presence or absence of a model leads to a fundamental taxonomy:

The tic-tac-toe player in this lecture is model-free with respect to its opponent: it has no model predicting what the opponent will do. Modern RL spans the whole spectrum—the most powerful systems often combine both approaches. AlphaGo Zero, for instance, learns a value function via self-play (model-free) and uses Monte Carlo Tree Search for planning at decision time (model-based).

1.6 When to Use Reinforcement Learning

RL is well-suited to problems in large environments when any of these hold:

1. A model of the environment is known, but an analytic solution is not available (e.g., the equations exist but are intractable).
2. Only a simulation model of the environment is given (simulation-based optimisation).
3. The only way to collect information about the environment is to interact with it—no offline dataset of correct actions exists.

1.7 Examples of Agent-Environment Pairs

Key Characteristics of Reinforcement Learning

RL differs from supervised learning in several important ways:

1. Reward-based interaction: Learning is driven by a single scalar reward signal from the environment. The feedback is evaluative (how good was that action?) rather than instructive (here is the correct action). This is a fundamental distinction: in supervised learning, a teacher explicitly says “this is the right answer”; in RL, the environment only says “that got you +5” or “that got you −2”.
2. Sequential decision making: The agent does not solve a one-shot prediction problem; it must choose a sequence of actions that interact with each other. The present action changes the next state, and the next state changes what actions are available later.
3. Delayed consequences: A reward (positive or negative) may arrive long after the action that caused it. Think of setting a trap in chess: the payoff arrives many moves later. This creates the credit assignment problem—deciding which earlier actions contributed to later success or failure.
4. Trial-and-error learning: The agent must try actions to discover their effects. There is no oracle telling it the “correct” action. The agent may know that an outcome was good, but it may not know which action should have been chosen instead.
5. Exploration vs. exploitation: The agent must balance using what it already knows (exploit) with trying new things to discover better strategies (explore). We will return to this in Section 6. This dilemma does not even arise in the purest forms of supervised or unsupervised learning.
6. Non-i.i.d. data: Successive states are highly correlated; the data distribution depends on the policy. This breaks many assumptions of supervised learning.
7. Uncertainty: The agent normally operates with incomplete knowledge of the environment. Outcomes may be stochastic—the same action may not always lead to the same result. RL explicitly considers the whole problem of a goal-directed agent interacting with an uncertain environment.

Rewards, Returns, and Value Functions

1.8 From Reward to Return

Maximizing the immediate reward $R_{t+1}$ is not enough. The agent should maximize the cumulative reward—called the return—starting from time $t$.

1.9 Policy: The Agent's Way of Working

Intuitively: the policy is “my way of working.” Given a situation, what do I do? Two different agents in the same state can choose different actions because they have different policies.

1.10 Value Function: Long-Term Desirability

1.11 A Two-State Toy Example

Consider an environment with only two states $S_1$ and $S_2$, and two actions: $L$ (left) and $R$ (right).

Suppose my policy $\pi$ in state $S_2$ always picks $R$ (i.e., I bump the wall). My trajectory from $S_1$ looks like:

The return from $S_1$ is small. But your policy might always choose $L$ from $S_2$, giving:

which has a much higher return. Hence:

1. Different policies $⟹$ different value functions.
2. Therefore, values are always with respect to a particular policy.

1.12 The Policy-Value Duality

A Worked Example: Learning Tic-Tac-Toe with RL

We now apply RL to a concrete game. This example is adapted from Sutton & Barto, Chapter 1, and it illustrates almost every idea from the lecture.

1.13 Problem Setup

Two players (agent vs. opponent) alternate placing $\times$ and $\circ$ on a $3\times 3$ grid. The agent plays $\times$. There are three possible outcomes:

• Agent wins $⟹$ reward $+1$.
• Agent loses $⟹$ reward $0$ (or $-1$).
• Draw $⟹$ reward $0$.

1.14 Why Not Just Use Exhaustive Search?

In the AI course you may study minimax search or alpha-beta pruning for games. These methods:

• Assume the opponent plays optimally.
• Search the entire game tree (or a heuristic-pruned version).
• Find the theoretically optimal move.

But what if the opponent is not optimal? A suboptimal opponent might have specific weaknesses we can exploit. RL learns to play against the opponent it actually faces, not an idealised optimal one.

RL is also scalable: exhaustive search is impossible for games like Go or StarCraft.

1.15 The Tabular Value Function

We maintain a table with one row per possible board state. Each row stores a single number $V(s)$ representing the current estimate of the value of that state.

Initialization:

• For states where the agent has already won (three $\times$’s in a line): set $V(s)=1$.
• For states where the opponent has won: set $V(s)=0$.
• For all other states: set $V(s)=0.5$ (we are uncertain—roughly 50/50).

This is called a tabular method: each state is one row, and updating one row does not affect any other row. Tabular methods are simple and powerful when the state space is small enough to enumerate. (For tic-tac-toe there are only a few thousand legal states; for chess there are $\sim 10^{43}$, so tables won't fit and we need deep learning.)

1.16 Choosing Moves: Greedy Action Selection

Suppose the opponent has just moved, giving the agent a board configuration $B$. From $B$, the agent has several possible moves leading to states $C_1,C_2,\dots ,C_k$.

The greedy (exploitation) move: look up $V(C_1),V(C_2),\dots ,V(C_k)$ in the table, and play the move that leads to the highest-valued state.

In the figure above: the opponent moved $A\to B$. The agent considers all moves from $B$ and chooses the one leading to a state with value $0.7$ (the highest among its options).

1.17 The Temporal-Difference (TD) Update Rule

After the agent makes a greedy move from state $A$ to a state $A^{\prime }$ (via the opponent and the agent’s greedy choice), it updates the value of $A$ to be closer to the value of $A^{\prime }$:

1.18 Bootstrapping and Backing Up Values

Notice that we update $V(A)$ using $V(A^{\prime })$, which is itself only an estimate. This is called bootstrapping: we learn an estimate from another estimate.

Initially every internal state has value $0.5$, so updates do little. But the values of terminal states ($1$ for a win, $0$ for a loss) are correct from the start. As games are played, terminal values gradually propagate backward through the table: states adjacent to wins get value above $0.5$, states adjacent to those get nudged up, and so on. Over many games, the entire table becomes informative.

Exploration vs. Exploitation

1.19 The Dilemma

Sutton & Barto emphasise that this issue has been intensively studied by mathematicians for many decades, yet remains unresolved—there is no universally optimal strategy for exploration. On a stochastic task, each action must be tried many times to gain a reliable estimate of its expected reward. If the agent only exploits, it may settle too early for a suboptimal action. If it only explores, it may fail to benefit from what it has already learned. Good reinforcement learning therefore requires a practical balance between both.

1.20 When NOT to Update: Exploration Moves

In the tic-tac-toe scheme described above:

• After an exploitation move, we apply the TD update—we are confident that the next state was chosen because of our value estimates, so it carries useful information about $V(A)$.
• After an exploration move, we do not update. The action was random, so the resulting next state tells us little about whether $A$ is good or bad under our current policy.

1.21 The Role of the Step Size $\alpha$

The learning rate $\alpha$ controls how quickly we trust new information:

1.22 A Common Exploration Strategy: $ϵ$-Greedy

A practical algorithm for balancing exploration and exploitation is $ϵ$-greedy:

Typically, $ϵ$ is large at the start of training (say $ϵ=0.3$) and decays toward a small value (say $0.01$) as the agent gains experience.

Putting It All Together

1.23 The General RL Recipe

1. Initialize a value function $V$ (or a Q-function $Q$, or a policy $\pi$).
2. Repeat for many episodes (games, trials, simulations):
   1. Observe the current state $S_t$.
   2. Choose an action $A_t$ (mostly greedy, occasionally exploratory).
   3. Receive reward $R_{t+1}$ and next state $S_{t+1}$.
   4. Update $V$ (or $Q$ or $\pi$) using a TD-style rule: $V(S_t)\leftarrow V(S_t)+\alpha [R_{t+1}+\gamma V(S_{t+1})-V(S_t)]$.
   5. Move on: $S_t\leftarrow S_{t+1}$.
3. Over time, the value function (and hence the implicit policy) converges to something good.

1.24 Sequential Decision Problems

The setup we have described is more formally called a Sequential Decision Problem (SDP). At every time step the agent must:

1. Observe the state.
2. Choose an action.
3. Receive a reward and a new state.

This may continue forever (continuing tasks) or stop at a terminal state (episodic tasks). Both will be formalised in the next lecture as Markov Decision Processes (MDPs).

Common Pitfalls and Clarifications

Lecture Takeaways

1.25 Historical Context

The field of reinforcement learning has deep roots. The term and modern framework trace back to the work of A. Harry Klopf in the late 1970s at Wright-Patterson Air Force Base. Klopf was dissatisfied with equilibrium-seeking models of intelligence and argued that maximizing systems—systems that actively try to maximize something—held the key to understanding natural intelligence. His ideas brought together Richard Sutton (then a Stanford undergraduate) and Andrew Barto (a newly-minted PhD at UMass Amherst) in 1979. Their collaboration, funded by AFOSR, produced the computational study of RL as we know it today.

However, the intellectual lineage goes back much further. In 1911, Edward Thorndike formulated the Law of Effect — arguably the first succinct expression of trial-and-error learning as a principle:

"Of several responses made to the same situation, those which are accompanied or closely followed by satisfaction to the animal will, other things being equal, be more firmly connected with the situation, so that, when it recurs, they will be more likely to recur; those which are accompanied or closely followed by discomfort to the animal will, other things being equal, have their connections with that situation weakened."

— Edward Thorndike, Animal Intelligence (1911)

In 1948, Alan Turing described what may be the earliest computational design for a learning system based on the Law of Effect — a "pleasure-pain system":

"When a configuration is reached for which the action is undetermined, a random choice for the missing data is made and the appropriate entry is made in the description, tentatively, and is applied. When a pain stimulus occurs all tentative entries are cancelled, and when a pleasure stimulus occurs they are all made permanent."

— Alan Turing, "Intelligent Machinery" (1948)

In the 1960s, Donald Michie built MENACE (Matchbox Educable Naughts and Crosses Engine) — a physical tic-tac-toe learner using matchboxes filled with coloured beads to represent state-action probabilities, with beads added or removed based on game outcomes. The BOXES system (Michie & Chambers, 1968) applied similar ideas to pole-balancing — one of the earliest reinforcement learning tasks under incomplete knowledge. Harry Klopf is the individual most responsible for reviving the trial-and-error research thread within AI in the 1970s, recognizing that the hedonic aspects of behaviour — the drive to achieve results from the environment — had been lost as researchers focused almost exclusively on supervised learning.

The field has since grown into one of the most active research areas in machine learning, with contributions from psychology, control theory, AI, and neuroscience. Key milestones include: TD-Gammon (Tesauro, 1992)—the first program to achieve world-champion level play using TD learning and neural networks; DQN (Mnih et al., 2015)—human-level Atari game play from raw pixels; AlphaGo (Silver et al., 2016)—defeating the world champion at Go; and AlphaGo Zero (2017)—learning superhuman Go without any human data.

1.26 Real-World Applications

Review of Key Terms

The following glossary summarizes essential terms required for reading Chapter 1 of Sutton & Barto and preparing for examinations:

1.27 Further & Required Reading

• Required Reading: Sutton, R. S., and Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press. Chapter 1, especially Sections 1.1 to 1.5 covering definitions, examples, core elements, and the tic-tac-toe illustration.
• Next Steps: Skim the book’s table of contents to prepare for Markov Decision Processes (MDPs), Bellman equations, dynamic programming, and TD learning.

1.28 Review & Self-Check Questions

Use these examination preparation and self-check questions to verify that you have absorbed the lecture:

1. Define reinforcement learning using the agent–environment interaction framework. Explain the roles of state, action, reward, and cumulative reward.
2. Compare reinforcement learning with supervised learning and unsupervised learning. Clearly distinguish instructive feedback from evaluative feedback.
3. Explain the four main elements of reinforcement learning: policy, reward signal, value function, and model. Why is the value function especially important for long-term decision-making?
4. Discuss the exploration–exploitation trade-off. Why can an agent fail if it only exploits current knowledge or only explores new actions?
5. In the tic-tac-toe example, explain how state values are initialized, how moves are selected, and how the temporal-difference update changes the value of an earlier state.
6. In one sentence, what distinguishes RL from supervised learning?
7. What is the difference between an immediate reward and a cumulative return?
8. Why does a state's value function strictly depend on the agent's policy?
9. Why does the basic TD update for tic-tac-toe not fire after exploratory moves?
10. What happens if the learning rate $\alpha$ is set to 0? What happens if it is set to 1?
11. Give an example from everyday life illustrating a delayed reward and credit assignment.
12. Why are tabular methods insufficient for problems with large state spaces like Go or Atari?

End of Lecture 1 Notes. In the next lecture we will formalise the agent–environment interaction as a Markov Decision Process (MDP) and study Bellman equations.