Skip to content
Tutorials Center
My learning

Topics

Lesson 88 of 111 ยท Reinforcement Learning

Reinforcement Learning Basics

Learn reinforcement learning from first principles: agents, rewards, MDPs, policies, discounting and exploration vs exploitation, with a NumPy bandit.

Supervised learning needs an answer key. Reinforcement learning (RL) does not have one. An agent (the learner) takes actions in an environment, and the environment answers with a new situation and a number called a reward. Nobody tells the agent which action was correct. It has to find out by trying things, noticing which ones led to more reward, and doing more of those. This is how you teach a dog a trick, how a program learns to play a game, and how a robot learns to walk.

This lesson builds the vocabulary and the basic ideas: the agent loop, Markov decision processes (MDPs), policies, value, discounting, and the central dilemma of exploration versus exploitation. We make the dilemma concrete with a runnable multi-armed bandit in NumPy. The next lesson, Q-Learning, SARSA and Model-Free Methods, learns to act in environments with many states. If you want neural networks in RL (DQN and policy gradients), that is covered in Neural Networks in Reinforcement Learning.

The agent loop

Agent Chooses an action.
Environment Responds with a new state.
Reward A number saying how well it went.
1 / 2

The agent loop

At every time step t, the cycle is the same:

  1. The agent observes the current state s.
  2. It picks an action a.
  3. The environment returns a reward r and the next state s'.
  4. The agent updates what it knows and repeats.
flowchart LR
    A["Agent"] -- "action a" --> E["Environment"]
    E -- "reward r" --> A
    E -- "next state s'" --> A

The loop of reinforcement learning: act, observe the reward and the new state, learn, repeat.

What makes RL different from the other learning types in this course is that the data depends on the agent's own choices. A classifier is trained on a fixed table. An RL agent decides which data it will see next, and rewards can be delayed: a chess move that wins the game 40 moves later gets no reward until the end. Working out which earlier actions deserve credit is the credit assignment problem.

Markov decision processes

Most RL problems are described as a Markov decision process (MDP), which has five parts:

Part Meaning Gridworld example
States S Situations the agent can be in Each square of the grid
Actions A What the agent can do Up, down, left, right
Transitions P(s' | s, a) How the environment moves Move one square (maybe slip)
Rewards R(s, a, s') Immediate feedback -1 per step, +10 at the goal
Discount ฮณ How much the future counts 0.9

The Markov property says the future depends only on the current state and action, not on the whole history. If the state includes everything relevant (the positions of all pieces on the board), you can ignore how you got there.

A policy ฯ€ is the agent's behavior: a mapping from states to actions (or to probabilities of actions). The goal is to find a policy that maximizes the expected return, the total reward over time:

G = rโ‚ + ฮณยทrโ‚‚ + ฮณยฒยทrโ‚ƒ + โ€ฆ

The discount factor ฮณ between 0 and 1 makes rewards in the near future worth more than the same reward later. With ฮณ = 0 the agent is short-sighted and only cares about the next reward; with ฮณ near 1 it plans far ahead. Discounting also keeps the sum finite for tasks that never end.

The value of a state under a policy, V(s), is the expected return when you start there and follow the policy. The action value Q(s, a) is the expected return after taking action a first. If you know Q for every action, the best policy is simple: pick the action with the highest Q. Almost every RL algorithm is a way of estimating these values.

Exploration versus exploitation

Suppose you have tried two restaurants near your office. One was good. Should you keep going there (exploit what you know) or try a third place that might be better, or might be bad (explore)? An agent faces the same choice at every step:

  • Only exploiting means it can get stuck with a mediocre option forever, because it never discovers the better one.
  • Only exploring means it keeps testing options and never cashes in on what it learned.

The cleanest way to study this trade-off removes states entirely. A multi-armed bandit is a row of slot machines (arms). Each arm pays a random reward with its own unknown average. Every step you pick one arm; the goal is the highest total reward. There is no next state, only the dilemma.

The simplest strategy is epsilon-greedy: with probability ฮต pick a random arm (explore), otherwise pick the arm with the best estimated average so far (exploit). The estimate is updated incrementally after each pull:

Q(a) โ† Q(a) + (r โˆ’ Q(a)) / N(a)

where N(a) counts how often arm a was pulled. That is just a running average written as an update, and the same "move the estimate toward the new observation" shape appears in every RL algorithm.

The experiment below creates 300 independent 10-armed bandits (each arm's true mean is drawn from a standard normal, rewards add noise with standard deviation 1), runs 1,000 steps on each, and compares three values of ฮต. It is vectorized across the 300 runs so it finishes in seconds. Printed numbers are averages over all runs.

Python Epsilon-greedy on a 10-armed bandit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The pure greedy agent (ฮต = 0) picks the best arm in only 30% of its late steps: it locks onto an early lucky arm and rarely leaves. A little exploration (ฮต = 0.01) helps, and ฮต = 0.1 identifies the best arm 79% of the time and earns the most reward in this run. Exploring costs something on every step (10% of pulls are random), yet it pays off because finding the best arm is worth far more. With more steps, a smaller ฮต eventually wins, which is why many agents lower ฮต over time.

Smarter exploration

Random exploration wastes pulls on arms already known to be poor. Two classic improvements spend exploration where uncertainty is highest:

  • Optimistic initial values. Start every Q at a high number such as 5. Every arm "disappoints" when first pulled, so the agent tries the others, and exploration fades by itself as estimates settle.
  • Upper confidence bound (UCB). Score each arm as its estimate plus an uncertainty bonus that shrinks the more it has been pulled: Q(a) + cยทโˆš(ln t / N(a)). Rarely-tried arms get a big bonus, so they get tried; well-known arms are judged on their average.

A third idea, Thompson sampling, keeps a probability distribution over each arm's value and picks the arm whose random draw is highest. It is popular in practice for online experiments such as ad selection.

In the next experiment we add the first two to the same bandits and track the regret, the reward you gave up compared with always pulling the best arm. Lower is better.

Python Optimistic start and UCB vs epsilon-greedy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Greedy never recovers: its regret per step stays near 0.55. Epsilon-greedy cuts that to 0.18 late in the run but never reaches zero, because it keeps exploring at random forever. The optimistic start is much better in the first 100 steps (0.30) and UCB is best overall: its late regret is about 0.02 and its total is roughly a quarter of epsilon-greedy's (60 versus 236). UCB explores in a targeted way, so almost none of its pulls are wasted once the arms are well known.

Bandits are not just a toy. A/B testing tools, news-feed ranking and ad selection use bandit algorithms to shift traffic toward the better variant while the test is still running, instead of waiting for a fixed-length test to end.

From bandits to full RL

A bandit has no states, so your action only affects the reward you get now. In a full MDP, an action also changes the state, which changes what you can do next. Now rewards are delayed and the value of a state depends on the future. The central tool is the Bellman equation, which writes a value in terms of the values of the next states:

V(s) = max over a of [ R(s, a) + ฮณ ยท V(s') ]

When you know the full MDP (transitions and rewards), you can solve for the values directly by repeating that equation until it stops changing. This is value iteration, a form of dynamic programming. The example below uses a tiny corridor of five squares, with a reward of +10 for reaching the right end and -1 per step. It shows the discounted return of a path and then lets value iteration compute V for every square.

Python Discounted return and value iteration

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With ฮณ = 0.9 the same path is worth 4.58, with ฮณ = 0 only the first step counts (-1), and with ฮณ = 1 everything counts equally (7). Value iteration converges in 5 sweeps: the goal-side square has the highest value (10, one step from the goal) and values fall by roughly a factor of 0.9 plus the step cost for each square farther away. The best action in every square is to move right, which you can read off the values with no further learning.

Value iteration needs the transition rules, which a real agent rarely has. Methods that learn from experience alone, without a model of the environment, are called model-free, and they are the subject of the next lesson.

Bellman equations, policy evaluation and policy iteration

The corridor above had no randomness: every action did exactly what it said. Most MDPs are stochastic, so the transition function P(s' | s, a) gives a probability for each next state, and the value of an action is an expectation over those outcomes. Two Bellman equations cover everything in this lesson.

For a fixed policy ฯ€, the Bellman expectation equation says that a state's value is the average, over the actions the policy might take and the states that might follow, of the reward plus the discounted value of the next state:

V_ฯ€(s) = ฮฃ_a ฯ€(a | s) ยท ฮฃ_s' P(s' | s, a) ยท [ R + ฮณ ยท V_ฯ€(s') ]

For the best possible policy, the Bellman optimality equation replaces the average over actions with a maximum:

V*(s) = max over a of ฮฃ_s' P(s' | s, a) ยท [ R + ฮณ ยท V*(s') ]

Turning those equations into repeated updates gives three planning algorithms, all of which need the full model:

  • Policy evaluation sweeps the expectation equation until V_ฯ€ stops changing. It answers "how good is this policy?".
  • Value iteration sweeps the optimality equation. It finds V* directly, and the optimal policy is whatever action is greedy with respect to it.
  • Policy iteration alternates two steps: evaluate the current policy completely, then improve it by acting greedily on those values. It repeats until the policy stops changing, which usually takes only a handful of rounds, although each round contains a full evaluation.

The program below builds a 4x4 "slippery" grid in which each move succeeds with probability 0.8 and slides sideways with probability 0.1 each way. Reaching G pays +1, falling into a hole H ends the episode with nothing, and ฮณ = 0.95. It runs value iteration and policy iteration, compares them, and evaluates a naive "always go right" policy for contrast.

Python Value iteration versus policy iteration on a slippery grid

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both methods find the same optimal policy and the same values, as the theory promises. Value iteration needed 26 sweeps of the whole grid, while policy iteration finished in 5 improvement rounds, each with its own evaluation inside. Read the value grid as a map of safety: the squares next to the goal are worth about 0.9 and 0.97, while squares by the holes are worth less, because a slide can end the episode. The optimal policy sometimes steps away from a hole and lets the slip push it where it wants to go. The naive policy is dramatically worse (about 0.002 at the start, against 0.531 for the optimal one), because it ends up pressed against the right wall, where a sideways slip eventually drops it into the hole at the edge of the second row.

Planning algorithms like these need the transition table. When the model is unknown, you estimate the same quantities from sampled experience, which is exactly what Q-learning and SARSA do. Another family skips values altogether and improves the policy directly: see Policy Gradients, REINFORCE and Actor-Critic.

Where RL is used, and its limits

RL has produced game-playing systems, robot control, data-center cooling, recommendation policies and the human-feedback stage that tunes large language models (how LLMs are trained). It also has real costs:

  • Sample hungry. Agents often need millions of attempts, which is fine in a simulator and impossible with real patients or real money.
  • Reward design is hard. Agents optimize exactly what you reward, including loopholes: a cleaning robot rewarded for "no visible mess" may learn to hide the mess.
  • Unstable. Small changes in settings can change results a lot, and results vary from run to run.
  • Often unnecessary. If you have labeled examples of good decisions, supervised learning is simpler and cheaper.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the main difference between reinforcement learning and supervised learning?

    In supervised learning every example comes with the right answer. In RL the agent only receives a reward, often delayed, and its actions decide what data it sees next.
  2. 2. An agent uses discount factor gamma = 0. How does it behave?

    With gamma = 0 every future term in the return is multiplied by zero, so only the next reward counts. Values near 1 make the agent far-sighted.
  3. 3. Why does a purely greedy agent (epsilon = 0) often do poorly on a bandit?

    Without exploration, an early lucky result can make a mediocre arm look best and the agent never tests the others.
  4. 4. What does the Bellman equation express?

    V(s) equals the best immediate reward plus gamma times the value of the next state. Value iteration applies this repeatedly until the values stop changing.

Summary

  • An RL agent acts, receives a reward and a new state, and learns to maximize the discounted return G = rโ‚ + ฮณยทrโ‚‚ + ฮณยฒยทrโ‚ƒ + โ€ฆ.
  • An MDP has states, actions, transitions, rewards and a discount; a policy maps states to actions; V and Q estimate expected return.
  • Exploration (trying unknown options) and exploitation (using the best known option) must be balanced.
  • Epsilon-greedy, optimistic initial values and UCB are simple ways to explore; regret measures what exploration costs.
  • Value iteration solves a known MDP using the Bellman equation; model-free methods learn from experience alone.
  • RL is powerful but sample hungry and sensitive to reward design; use supervised learning when you have labeled decisions.

Continue with Q-Learning, SARSA and Model-Free Methods.