Markov Chains and the Explore-Exploit Trade-off in Python

The concept in plain words

AI often has to act under uncertainty. A Markov chain models how a system moves between states with fixed probabilities, and a multi-armed bandit shows the core choice of reinforcement learning: try something new or use what has worked best so far.

Predict future states with a Markov chain and balance exploring and exploiting with an epsilon-greedy bandit.

Key ideas

In a Markov chain the next state depends only on the current state.
The transition probabilities out of one state always add up to 1.
Exploring finds better options; exploiting earns rewards from the best known option.
Epsilon controls the balance: a larger epsilon explores more.

When should you use it?

Understand what happens inside neural networks and AI libraries.
Learn the idea before you implement it in the matching challenges.
Prepare for machine learning courses, interviews and projects.

See it in action

Change the weather transition probabilities to see where the chain settles. Press Play to let the bandit learn which machine pays more.

Example code

Run code →

main.py

import random

# Markov chain: tomorrow's weather depends only on today's.
transitions = {"sunny": {"sunny": 0.8, "rainy": 0.2}, "rainy": {"sunny": 0.4, "rainy": 0.6}}
dist = {"sunny": 1.0, "rainy": 0.0}
for day in range(1, 4):
    dist = {s: sum(dist[p] * transitions[p][s] for p in dist) for s in dist}
    print(f"day {day}:", {s: round(v, 3) for s, v in dist.items()})

# Epsilon-greedy bandit: usually pick the best arm so far, sometimes explore.
random.seed(1)
true_payouts = [0.3, 0.7]
counts, totals = [0, 0], [0.0, 0.0]
epsilon = 0.1
for _ in range(500):
    if random.random() < epsilon or 0 in counts:
        arm = random.randrange(2)                                  # explore
    else:
        arm = max(range(2), key=lambda a: totals[a] / counts[a])  # exploit
    reward = 1 if random.random() < true_payouts[arm] else 0
    counts[arm] += 1
    totals[arm] += reward
print("pulls per arm:", counts)
print("estimated payouts:", [round(t / c, 2) for t, c in zip(totals, counts)])

Expected output

day 1: {'sunny': 0.8, 'rainy': 0.2}
day 2: {'sunny': 0.72, 'rainy': 0.28}
day 3: {'sunny': 0.688, 'rainy': 0.312}
pulls per arm: [25, 475]
estimated payouts: [0.16, 0.7]

How it works

Each day the new probabilities are the old ones multiplied by the transition probabilities, so sunny falls from 1.0 to 0.688 over three days. The bandit picks a random arm 10% of the time and otherwise pulls the arm with the best average so far; it soon spends most pulls on the better arm and estimates its payout at about 0.7.

Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.

Practice exercises

Modify the runnable example with the exercises below to build understanding beyond copying the result.

Change the inputs or weights and predict the output before running.
Print the intermediate values to follow each step of the calculation.
Solve the linked challenges below to implement the idea yourself.

Run in Python IDE →

Practice with a challenge

Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.

All challenges