The agent–environment loop

A gambler faces two levers: five pulls of the left lever paid 0, 1, 0, 0, 1, while four pulls of the right lever paid 0, 0, 0, 1. The left lever has averaged 0.4 per pull and the right 0.25, so the left looks better.

The chapter asks how a learner picks actions from payouts alone, and the two levers show the shape of the answer. Nobody tells the gambler which lever is better, and no row of a notebook records the correct choice. The only feedback is the payout after each pull. That feedback arrives only after the action, and it never says what the right action was [S:83:23]. !The agent sees a state, chooses an action, and receives a reward and the next state; then the loop repeats. The dashed line is the agent-environment boundary, and it does not follow the robot's skin: the agent's sensors and motors sit on the environment side, because the agent cannot change them at will. The figure is schematic. Status: schematic.

Reinforcement learning is learning what to do so as to maximize a numerical reward signal [S:83:23], and the learner is not told which actions to take but must discover which ones yield the most reward by trying them [S:83:23]. Trial-and-error search and delayed reward, which arrives after many steps, are the two features that distinguish it from other kinds of learning [S:83:23-24]. The interaction is the point: an infant waving its arms learns how the world responds, without a teacher [S:83:23]. !A game pays only at the end. The move that earned the reward may sit many steps back, and no label marks it: the three arrows run back to earlier moves, and the earliest end carries a question mark. Credit assignment is the problem of deciding which earlier action the final number belongs to, and the further back the credit must travel, the harder the problem. The figure is schematic. Status: schematic.

An agent is the learner and decision maker, while the environment is everything outside the agent that it interacts with [S:83:69]. At each step the agent receives a state, a description of the situation it faces, and selects an action from those available. The environment then returns a reward, one number, and a new state [S:83:70]. A state can be a board position, a list of sensor readings, or a row of numbers, as long as it carries what the next step depends on.

A policy is the rule that maps states to actions, or to probabilities over actions [S:83:80], and the loop runs state, action, reward, next state, then repeats [S:83:70]. Picture a game of hot and cold: you step, a voice says warmer or colder, and you step again. The comparison breaks because hot and cold answers after every step, while a real reward may arrive many steps later.

The boundary between agent and environment is not the skin of a robot, because anything the agent cannot change arbitrarily counts as part of the environment [S:83:72]. The agent's own body, its motors and sensors, usually sits on the environment side of that line [S:83:72]. Drawing the line in the wrong place changes the problem, so the choice deserves care.

Delayed reward is the second difference from ordinary trial and error. Imagine a chess program that learns whether it won only at the end of the game. The final payout must then be credited to moves made much earlier, a problem called credit assignment [S:83:69]. The further back the credit must travel, the harder the learning, and a reward that arrives at the end of a long game therefore teaches slowly.

This is not supervised learning, because supervised learning receives a training set of labelled examples with the correct answer attached [S:83:24]. A gambler has no labels, only payouts. The agent's own actions also change which situations it meets next, so the data is not fixed in advance, and the difference matters most in new territory where nobody knows the right action.

The loop forces a choice between exploration, trying actions to learn about them, and exploitation, using the action that has paid best so far [S:83:25]. Neither alone works, because an agent that only exploits never finds the better lever while an agent that only explores never collects [S:83:25]. A problem with one state and several actions is called a bandit problem, a name taken from the slot machine, or one-armed bandit. It is the smallest version of this trade-off.

Worked example. The left lever paid twice in five pulls, so its estimated value is 2/5 = 0.4, while the right lever paid once in four pulls, so its estimate is 1/4 = 0.25. A greedy rule, which always takes the action with the best estimate so far, picks the left lever.

Four pulls is thin evidence, though: a lever that pays one time in four could be better than one that pays two times in five. A common compromise is epsilon-greedy: with probability epsilon it explores, and otherwise it acts greedily. With epsilon 0.1, one pull in ten takes the exploration branch and the other nine take the greedy action. With two actions, the exploration branch lands on the greedy action half the time, so the greedy action is chosen on nineteen pulls in twenty. If the next pull of the right lever pays 1, its estimate rises to 2/5 = 0.4 and the two levers tie.

The loop has a sharp edge. A reward is one number chosen by a designer, and the agent will pursue that number rather than the outcome the designer intended [S:83:76]. A robot rewarded for collecting cans may learn to knock over the bin. The framework also assumes the state tells the agent enough to decide. When it does not, the loop needs memory, which is the next section's problem.

The formal statement. A finite MDP is a tuple of states, actions, rewards, a dynamics function and a discount rate. The dynamics function $p(\text{next state},\text{reward}\mid \text{state},\text{action})$ gives the probability of each next state and reward pair [S:83:70-71]. For each state and action, those probabilities sum to one over all pairs [S:83:70-71]. The policy $\pi (\text{action}\mid \text{state})$ is a probability distribution over actions [S:83:80]. The loop is the resulting trajectory of states, actions and rewards [S:83:70]. Four conditions carry the definition. The sets of states, actions and rewards are finite [S:83:70]; time is discrete; the state has the Markov property; and the dynamics do not change with time. Finiteness of the reward set makes each reward a bounded real number, but boundedness alone, with an infinite reward set, does not give a finite MDP: the dynamics would no longer be a finite table.

The algorithm. Epsilon-greedy estimates each action value by a sample average. With probability one minus epsilon it picks the best estimate, and with probability epsilon it picks uniformly among the $k$ actions. Suppose the greedy action is also the best one. The probability of picking it is then $1-\text{epsilon}+\text{epsilon}/k$. The omitted step is the assumption that the greedy action is the best one. When that fails, the probability of picking the best action is only $\text{epsilon}/k$.

The edge case. Take $k=2$ and epsilon equal to 0.1. The rule picks the greedy action with probability 0.95, so one pull in twenty goes elsewhere. One minus epsilon is 90%, the chance of taking the greedy branch before the exploration branch is resolved; the 95% includes the half of the exploration pulls that also land on the greedy action. That fraction never falls to zero. The book states the limit: every action is sampled infinitely often, so the probability of the optimal action converges to slightly above one minus epsilon [S:83:50]. L1 called epsilon equal to 0.1 a compromise and stopped there. The hidden cost is a permanent tax on the average reward, and epsilon sets the size of the tax. A decaying schedule removes the tax. A constant schedule does not.

What L1 hid. L1 said the agent must explore and exploit at the same time. That is true, and it hid the fact that the balance has a price you can compute. The simplification was safe because L1's job was to show that the conflict exists, not to promise a rate. L1 also hid that the guarantee is asymptotic: every action is sampled infinitely often only in the limit [S:83:50].

Where the analogy breaks. In hot and cold, the voice says warmer or colder. That is a direction, because it tells you which way to move. A reward is one number attached to the action taken. With many actions it gives no direction at all, and with delayed reward it does not even say which action earned it. That gap is why the bandit needs exploration and the childhood game does not.

Original sources. The framing of learning as interaction with an environment opens Sutton and Barto's introduction [S:83:23]. They name trial-and-error search and delayed reward as the two distinguishing features [S:83:23-24]. They also separate evaluative from instructive feedback: evaluative feedback depends on the action taken, instructive feedback does not [S:83:47]. The same book introduces the one-state case as the k-armed bandit, named by analogy to a slot machine [S:83:48]. Szepesvári states the same loop as a control problem, learning to maximise a numerical value that represents a long-term objective [S:80:3]. The modern treatment replaces the informal trade-off with regret. Regret is the loss against the best fixed action, and a good learner keeps it below linear growth in the number of rounds [S:81:20].

An open question. For stochastic stationary bandits the rate is settled. Worst-case regret grows at least as fast as the square root of the number of rounds, and some policies attain that rate [S:81:20]. No matching pair of bounds exists for a general MDP with a large state space and function approximation. The field has algorithms that work in practice and partial theory, not a tight characterisation. Evidence that would settle it: a lower bound proved for a stated function-approximation class, plus an algorithm that attains the bound with a matching constant.

A frontier result. AlphaGo Zero learns from games it plays against itself [S:286:1]. It trains one network on two signals. The value head predicts the game winner $z$, which is observed only when the game ends; the policy head matches the search probabilities $\pi$ that the tree search produces at each position [S:286:1] [S:286:4]. The game outcome supplies the delayed reward, while the search distribution is an immediate, non-reward supervisory signal. That is the agent-environment loop with delayed reward on one side and a teacher that is not a reward on the other, at a scale where the state is a board position. The result depends on the loop, not on a labelled dataset.

What to read next. Read Chapter 2 of Sutton and Barto for the bandit version of the trade-off and the epsilon-greedy analysis [S:83:48]. Read Chapter 1 of Lattimore and Szepesvári for the regret definition and the square-root rate [S:81:20]. Then read the overview chapter of Szepesvári's short book, which states the loop as a control problem and maps the algorithms that follow [S:80:3].