Machine Learning

Imperial College London

Nuri Cingillioglu

Part 7: Agency & Evolution

Do or do not, there is no try. Or is there?

Agency

Real biological intelligence does not passively categorise static image datasets.

An organism acts, probes, and navigates through an uncertain environment:

Animal Conditioning

Classical Conditioning (Ivan Pavlov, 1904)

• Passive associative prediction: An animal learns correlations between neutral cues (metronome / bell) and unconditioned stimuli (food).

Animal Conditioning

Instrumental Conditioning & The Law of Effect (Edward Thorndike, 1898)

• Active trial-and-error discovery: A cat trapped inside a puzzle box claws haphazardly until accidentally tripping the latch.
• The Law of Effect: Actions followed by satisfying states are stamped into memory; actions followed by discomfort are extinguished.

My 2 year old niece randomly touches everything in the house until she gets hurt...

Thorndike's Puzzle Box (1898)

The PhD student randomly tries different things until something works. Over repeated trials, they learn to publish more papers.

Why is RL Difficult?

1. The Credit Assignment Problem
When an agent wins a game of chess after 60 moves, which specific move was responsible for victory? The decisive move may have occurred 40 steps earlier.

2. Non-Stationary, Non-i.i.d. Data
In supervised learning, samples are identically distributed. In RL, the agent's policy directly determines the data it collects:

Change the policy, and the entire training distribution shifts...

3. The Exploration vs. Exploitation Trade-off
To discover high rewards, the agent must venture into the unknown. But to maximise cumulative score, it must exploit what it already knows works.

Food at Imperial

• Exploit: Visit your dependable college café. You are guaranteed a solid lunch ().
• Explore: Try a new outlet. It might be awful (), or it might be magnificent ().

The Multi-Armed Bandit

To investigate exploration vs. exploitation, we define the -Armed Bandit Problem:

Imagine standing before slot machines (arms) :

1. At each step , the agent pulls an arm .
2. The arm delivers a numerical reward with an unknown true average payoff:

3. The true averages are completely hidden from the agent!

The objective is simply to maximise total cumulative reward over steps:

The Dilemma: You must explore unfamiliar arms to discover which is highest, but exploit the current best arm to accumulate reward

Payoff Distributions

We estimate the Value (Quality) of each arm by taking the sample average of the rewards received when pulling that arm:

where is the total number of times arm has been selected.

By the Law of Large Numbers, as , our estimate converges to the true payoff: .

Incremental Value Updates

Computing by summing all past rewards requires storing every historical pull in memory.

Instead, let's derive an incremental update rule for an arm after receiving its -th reward :

WHOA! This is our usual update rule where the bracketed term is the prediction error:

Why this works?

The key term you are looking for is the law of large numbers. As , the estimate converges to the true mean .

Which means you eventually learn, this is the trial and error process.

Action Selection

How should the agent choose which arm to pull given its current estimates ?

1. -Greedy Selection
With probability , exploit the best arm; with probability , explore uniformly at random:

2. Softmax (Boltzmann) Selection
Convert value estimates into smooth selection probabilities via temperature :

Notice that we have a toolkit like softmax that keeps on appearing in different areas of AI.

Interactive Multi-Armed Bandit Playground

• State : The agent's current sensory representation.
• Action : The agent's selected motor command.
• Reward : Scalar evaluative feedback emitted by the environment.
• Next State : The environment transitions into a new state.

Markov Decision Processes (MDP)

Bandits are stateless. In real tasks, actions change your state in the world.

A discrete Markov Decision Process (MDP) is formalised as a 4-tuple:

• : The set of all valid environmental states.
• : The set of all valid agent actions.
• : Joint transition-reward dynamics:
  Given state and action , the environment determines the next state and reward .
• : Temporal discount factor.

Some gymnastics, what is and ?

The Markov Property

"The future is conditionally independent of the past given the present."

Mathematically, the transition probability distribution satisfies:

What does this mean intuitively?

• The current state is sufficient to predict the future.
• You do not need to record the full history of past moves to predict the future.
• If an environment violates this (e.g., poker with hidden cards or a robot lacking velocity sensors), it is a Partially Observable MDP (POMDP).

Randomness in RL

Reinforcement learning has two distinct random actors interacting in a closed loop:

1. The Agent (Policy ): Selects an action with probability:

2. The Environment (Dynamics ): Simultaneously determines where you land and what reward you receive:

Everything in RL is about these: controls the agent, while governs the world.

From Bandits to Sequential Decisions

The bandit update moves an estimate towards the observed reward:

In a MDP, the action also takes us to . What is the target?

Tabular Q-Learning (Watkins, 1989)

Christopher Watkins formulated -Learning, an off-policy model-free TD control algorithm. When the agent takes action in state , receives reward , and lands in state :

• Off-Policy: The agent acts using an exploratory policy (e.g. -greedy), but updates towards the greedy maximum .
• Model-Free: The agent does not need to know the transition dynamics in advance. It learns purely from experience.

Step-by-Step Manual Trace on a Toy Grid

Let's manually compute a single Q-learning update step on a grid:

1. Prior Values: Agent is at with .
2. Action & Outcome: Agent moves RIGHT to , receives step cost .
3. Target Estimation: In state , the best action is UP towards the goal, with .
4. TD Arithmetic ():

Q-Learning Playground

Show me the code: Q-learning

import gymnasium as gym
import numpy as np

env = gym.make("FrozenLake-v1", is_slippery=False)
Q = np.zeros((env.observation_space.n, env.action_space.n))

alpha, gamma, epsilon = 0.2, 0.95, 0.15
episodes = 500

for ep in range(episodes):
    state, _ = env.reset()
    done = False
    
    while not done:
        # Epsilon-greedy action selection
        if np.random.rand() < epsilon:
            action = env.action_space.sample()
        else:
            action = np.argmax(Q[state])
            
        next_state, reward, terminated, truncated, _ = env.step(action)
        done = terminated or truncated
        
        # Bellman TD error update
        td_target = reward + gamma * np.max(Q[next_state]) * (not done)
        td_error = td_target - Q[state, action]
        Q[state, action] += alpha * td_error
        
        state = next_state

Where does this target come from???

In the multi-armed bandit, the target was intuitive:

In -learning, the target looks oddly specific:

Why this combination?

• Why the immediate reward ?
• Why discounted by ?
• Why the maximum over next actions ?

Just like in bandits, this target is a single sample of an underlying expectation.

Cumulative Discounted Return

We want to maximise the cumulative discounted return over time:

where ensures convergence for bounded reward sequences, see Appendix.

• (Short-sighted): Only cares about the very next reward ().
• (Far-sighted): Weighs future rewards almost as heavily as immediate ones.

Our goal is to find an optimal policy that maximises expected return from every state:

Constructing the Expectation: and

State-Value Function
The expected return starting in state and following policy thereafter:

Action-Value Function
The expected return starting in state , taking action , and following thereafter:

Using the environment's joint distribution , they are connected by:

The Bellman Equation

Richard Bellman (1957) formulated the recursive definition:

Substituting the recursive definition into gives the Bellman Equation:

Bootstrapping: The value of where you are today equals the expected immediate reward, plus the discounted value of where you land next. See appendix for derivation.

Bellman Optimality

Our goal is to find an optimal policy that maximises expected return:

1. Greedy choice now: The optimal value of a state is achieved by taking the best available action:

2. Optimal future: Take action now, then act optimally from onward:

Bellman Optimality Equation for

Substituting into identity (2) yields:

In explicit transition probability form:

From Expectation to Sample Target

Look at the right-hand side of the Bellman Optimality Equation:

This expectation averages over all possible next states and rewards weighted by .

• In real life, an agent does not know the transition dynamics of the universe!

From Expectation to Sample Target

• So we sample: The agent executes action in state , and the environment returns one single sample:

• Replacing the expectation with this single sample (and using current for unknown ):

Temporal Difference (TD) Learning

Updating an estimate towards a target formed by taking a 1-step sample and bootstrapping from existing estimates is called Temporal Difference (TD) Learning.

Formulated by Richard Sutton (1988), the update rule is driven by the discrepancy between expectation and reality:

Here is the Temporal Difference Error:

The Curse of Dimensionality

So why can't we use tabular Q-learning to drive an autonomous car?

• An Atari 2600 screen has pixels with 256 colour values states!

Bridge to Deep RL: Function Approximation

To scale beyond discrete grids, we replace the lookup table with a differentiable parametric function:

Instead of cell updates, we optimise mean squared error via gradient descent:

where the expectation is over transition tuples sampled from the replay buffer .

DQN (Mnih et al., DeepMind 2015): Played 49 Atari games directly from raw pixels.
AlphaGo / MuZero (Silver et al., 2016–2020): Mastered Go, Chess, and Shogi defeating human world champions through policy iteration + Monte Carlo Tree Search.

Dopamine as Temporal Difference Error

In 1997, Wolfram Schultz, Peter Dayan, and Read Montague discovered that:

Dopamine neurons do NOT just encode reward itself.

In many circuits, they encode the discrepancy between expected and actual reward the TD Error!

The Dopamine Response

Schultz recorded dopamine firing in macaque monkeys across three distinct regimes:

1. Unexpected Reward ()

• A juice drop is delivered without prior warning.
• , . Remember, .
• Dopamine neurons fire a burst of action potentials.

2. Conditioned Cue Learned ( at Reward)

• A light turns on, 2 seconds later juice arrives.
• As the monkey learns, the positive burst shifts backward in time to the earliest predictive cue matching the prediction.
• At the moment the juice arrives, expectation matches reality (). Firing stays at baseline.

3. Reward Omitted ()

• The light turns on, but juice is withheld.
• , .
• At the exact millisecond juice was anticipated, dopamine firing drops to an inhibitory silence below baseline. Utter disappointment...

Now imagine all the things we don't know about how our brain works and the amazing natural world

Two Cognitive Modes in the Brain

Neuroscience and artificial intelligence converge on two parallel control loops:

Questions

Transition: The Limits of Lifetime Learning

Reinforcement Learning provides a powerful model of lifetime learning (ontogeny).

However, consider how biological brains actually operate:

• A newborn gazelle can stand and run within 30 minutes of birth.
• It did not initialise its synaptic weights to random Gaussian noise and run millions of backpropagation gradient steps!
• Its motor architecture, reflexes, and body plan were sculpted across millions of years by Evolution.

"What we learn during a lifetime is constrained and enabled by what natural selection optimised across eons."

Evolution & Derivative-Free Search

Two Clocks of Intelligence: Phylogeny vs. Ontogeny

The Non-Differentiable World

Backpropagation requires computing analytical gradients .

What happens when gradients do not exist?

1. Non-Differentiable Functions: Step functions, discrete hardware switches, branching code execution.
2. Black-Box Environments: Proprietary physics simulators, economic markets, wet-lab biological assays.
3. Deceptive & Rugged Surfaces: Surfaces riddled with sharp local traps where gradients point directly away from the global optimum.

Gradient Descent vs. Evolution

Evolution

Evolutionary Algorithms treat the task as a derivative-free black-box optimisation:

Interactive Evolutionary Walkers

1. Population

A population is a set of candidate solutions in search space .

A walker:
Each individual encodes both morphology and gait:

• Discrete Genes (Body Morphology):
  • Leg Count number of two-jointed limbs attached to the chassis (starts at ).
  • Foot Shape ankle geometry (Narrow Peg, Flat Pad, or Curved Ski).
• Continuous Genes (Kinematics & Proportions):
  • Leg Length limb ground clearance over uneven rocks.
  • Stride Angle & Step Frequency .
  • Phase Shift inter-leg phase offset driving.

2. Fitness Function

The fitness function is a scalar-valued evaluation of how well a candidate solution performs in the environment:

Evaluating the Walker :

1. Tip-Over Failure: If torso tilt exceeds () or the body crashes into the rocks, the walker tips over and immediately fails at tick .
2. Scalar Fitness: Rewards forward distance and upright balance .

What is the fitness function of nature?

3. Selection

How do we decide which individuals reproduce?

1. Fitness-Proportionate (Roulette Wheel)

But, if one "super-individual" has higher fitness early on, it takes over the gene pool immediately local optima.

2. Tournament Selection (-Tournament)
Sample random individuals; the highest-fitness among the wins reproduction rights.

3. Truncation Selection
Keep top percent of population and discard the rest.

4. Genetic Operators: Crossover & Mutation

We also keep the best individual (solution) after each generation (elitism).

The real evolution

In biological systems, genetic operators act directly on chromosomes and DNA sequences:

Minimal Genetic Algorithm in Python

import numpy as np

def fitness(x):
    # Inverted Rastrigin function (optimum at x = [0, 0])
    return -(10 * len(x) + np.sum(x**2 - 10 * np.cos(2 * np.pi * x)))

pop_size, d, gens = 50, 2, 60
pop = np.random.uniform(-3.0, 3.0, size=(pop_size, d))

for gen in range(gens):
    scores = np.array([fitness(ind) for ind in pop])
    best_idx = np.argmax(scores)
    
    # Elitism: carry over the best individual
    new_pop = [pop[best_idx].copy()]
    
    while len(new_pop) < pop_size:
        # Tournament selection (k = 3)
        cand_idx = np.random.choice(pop_size, size=3, replace=False)
        parent1 = pop[cand_idx[np.argmax(scores[cand_idx])]]
        cand_idx = np.random.choice(pop_size, size=3, replace=False)
        parent2 = pop[cand_idx[np.argmax(scores[cand_idx])]]
        
        # Arithmetic crossover
        alpha = np.random.rand()
        child = alpha * parent1 + (1 - alpha) * parent2
        
        # Gaussian mutation
        if np.random.rand() < 0.2:
            child += np.random.normal(0, 0.3, size=d)
            
        new_pop.append(child)
    pop = np.array(new_pop)

Evolution Strategies (ES)

Instead of discrete chromosomes, ES optimise continuous real-valued parameters without gradients:

1. Perturbation (Candidate Sampling): Sample a population of mutant vectors by adding isotropic Gaussian noise to the current parameter estimate :

   where is the mutation step size (search radius).

2. Evaluation: Evaluate fitness for each candidate in the environment.

3. Recombine: Update in proportion to candidate fitness:
   where is the learning rate. Mutations yielding higher fitness pull towards them.

Covariance Matrix Adaptation (CMA-ES)

CMA-ES (Hansen, 2001) adapts both the mean and covariance :

The Problem with Objectives

So far, we define an objective function and climb the gradient, but this can be deceptive:

Novelty Search

Lehman & Stanley proposed an audacious paradigm: Novelty Search.

"To find the highest mountain, don't look up—explore the terrain."

1. Discard the Objective Function: The algorithm ignores performance completely
2. Define a Behavioural Characterisation : A descriptor of how the agent behaves (e.g. final coordinate reached in the maze).
3. Reward Behavioural Sparseness :
   where are the -nearest neighbours in an archive of behaviours.

Think of having a team of diverse people versus all VIM users.

Deceptive Maze: A Toy Example

The Robot & Genome:
Starts at and executes a sequence of steering commands .
Traces a continuous trajectory through the maze, stopping if colliding with walls.

Behavioural Characterisation :
We define behaviour simply as the robot's final landing coordinate: .
The genome is how it steered; the behaviour is where it ended up.

Objective Fitness vs. Novelty Search:

• Objective (): Pulls the swarm directly against the wall closest to the goal, trapping all individuals in the cul-de-sac.
• Novelty (): Once the dead end fills up, it is no longer novel. The swarm is pushed outward to explore unvisited corridors—bypassing the trap!

Deceptive Maze & Novelty Search

Minimal Novelty Search in Python

import numpy as np

def simulate(genes, start=(1.0, 2.0)):
    x, y, heading = start[0], start[1], 0.0
    for steer in genes:
        heading += steer
        nx, ny = x + 0.8 * np.cos(heading), y + 0.8 * np.sin(heading)
        # Cul-de-sac wall blocking direct path (x in [3.8, 4.2], y < 6.0)
        if not (3.8 < nx < 4.2 and ny < 6.0) and (0 < nx < 10) and (0 < ny < 10):
            x, y = nx, ny
    return np.array([x, y])  # Behaviour b(x) = terminal landing coordinate

def novelty(b, archive, k=5):
    if len(archive) < k:
        return 1.0
    dists = np.linalg.norm(archive - b, axis=1)
    return np.mean(np.sort(dists)[:k])

pop_size, num_steps, gens = 40, 15, 30
pop = np.random.uniform(-0.5, 0.5, size=(pop_size, num_steps))
archive = []

for gen in range(gens):
    behaviors = np.array([simulate(ind) for ind in pop])
    scores = np.array([novelty(b, np.array(archive)) for b in behaviors])
    
    for b, s in zip(behaviors, scores):
        if s > 1.2 or len(archive) < 5:
            archive.append(b)
            
    new_pop = [pop[np.argmax(scores)].copy()]
    while len(new_pop) < pop_size:
        cands = np.random.choice(pop_size, size=3, replace=False)
        parent = pop[cands[np.argmax(scores[cands])]]
        child = parent + (np.random.rand(num_steps) < 0.25) * np.random.normal(0, 0.4, num_steps)
        new_pop.append(child)
    pop = np.array(new_pop)

Quality-Diversity (QD) Algorithms

Can we combine the exploratory power of Novelty with high performance?

• Objective Search: Maximises fitness , but gets trapped in deceptive local optima.
• Novelty Search: Discovers diverse behaviours , but ignores quality.

Quality-Diversity

Instead of finding a single optimum, find an entire repertoire of diverse, high-performing solutions:

• MAP-Elites (Mouret & Clune, 2015): Offspring mutate and compete locally within their behavioural niche and each niche has its own elite individual.

• Robotic Resilience (Cully et al., Nature 2015): A 6-legged robot suffered a broken leg, queried its pre-computed MAP-Elites repertoire, and discovered an effective compensatory limp in minutes.

Modern Neuroevolution

Can evolutionary algorithms compete with deep backpropagation on complex tasks?

1. OpenAI Evolution Strategies (Salimans et al., 2017)

• Evolved continuous neural network controllers for Atari 2600 and 3D humanoid locomotion.
• Evaluated hundreds of mutated policy vectors in parallel across 1,440 CPU cores.
• Achieved linear speedup with zero backpropagation communication overhead.

2. Evolutionary Neural Architecture Search (NAS)

• Algorithms like NEAT (Stanley & Miikkulainen, 2002) and AmoebaNet (Real et al., Google 2019) evolve both network topology and layer connectivity.
• Discovered vision backbones that surpassed hand-designed human architectures.

Where is my artificial brain?

I think we faired better this time. At least the numbers game was inspired by or connected to the real thing.

AI ML Numbers game

Next Part: The ethics of it all, should we be doing this, and what are the consequences of our actions?