The RL Problem and the Agent-Environment Loop

The agent-environment loop is the formal interaction protocol of reinforcement learning. Time is divided into discrete steps $t = 0, 1, 2, \dots$. At each step $t$, the environment presents the agent with a state $S_t \in \mathcal{S}$, a description of the current situation. The agent, using its internal decision rule, selects an action $A_t \in \mathcal{A}(S_t)$ from the set of actions available in that state. The environment then responds with two things: a numerical reward $R_{t+1} \in \mathbb{R}$, a scalar signal indicating how good that action was, and a new state $S_{t+1}$. This produces a sequence of experience:

Everything the agent knows about the world comes through this stream. It never gets a labeled "correct action" the way a supervised learner gets a labeled example. It only gets to see the consequences, in the form of rewards and new states, of the actions it actually chose. The agent's decision rule is called a policy, denoted $\pi$. A deterministic policy is a function $\pi: \mathcal{S} \to \mathcal{A}$ mapping each state to a single action. A stochastic policy is a conditional distribution $\pi(a \mid s) = \Pr(A_t = a \mid S_t = s)$, giving the probability of choosing each action in each state. Stochastic policies matter because, as later articles on the Exploration-Exploitation Dilemma discuss, always picking the same action can trap an agent in a suboptimal routine; some randomness lets it keep discovering better options. The environment, for its part, is characterized by its dynamics: the (possibly unknown) rule that determines the distribution of $R_{t+1}$ and $S_{t+1}$ given $S_t$ and $A_t$. In the cleanest and most widely studied case, this rule depends only on the current state and action, not on the full history — a property called the Markov Property, which will be made precise separately. For now, the loop is defined generally enough to allow environments whose dynamics are deterministic, stochastic, known to the agent, or completely unknown, since RL algorithms differ mainly in what they assume about this. The agent's ultimate goal is not to maximize any single reward $R_{t+1}$, but the cumulative reward over an episode or over time, a quantity formalized later as the return. The loop is simply the mechanism that generates the data — states, actions, rewards — from which the agent must learn to act well.

The loop is best understood as a synchronous exchange: the environment "moves first" by presenting a state, then the agent moves, then the environment moves again. Concretely, one full episode of interaction unfolds as follows. 1. The environment is initialized, producing an initial state $S_0$ (this may be fixed or drawn from a start-state distribution). 2. At each time step $t$, the agent observes $S_t$. 3. The agent selects an action $A_t$ according to its policy $\pi$, either $A_t = \pi(S_t)$ (deterministic) or $A_t \sim \pi(\cdot \mid S_t)$ (stochastic). 4. The environment computes the next reward $R_{t+1}$ and next state $S_{t+1}$, based on its (possibly hidden) transition dynamics. 5. The agent receives $(R_{t+1}, S_{t+1})$ and may update its internal knowledge (value estimates, policy parameters, etc.). 6. If $S_{t+1}$ is a designated terminal state, the episode ends; otherwise the loop returns to step 2 with $t \gets t+1$. Some environments are episodic — they naturally terminate (a chess game ends in checkmate; a maze run ends at the goal) — and some are continuing, running forever without a natural terminal state (a thermostat regulating temperature indefinitely). Both are modeled by the same loop; continuing tasks simply never reach step 6's termination branch, and their return must be handled specially, as discussed under returns. The pseudocode below expresses this cycle in a language-agnostic way that is faithful to how virtually every RL codebase is structured, from tabular Q-learning to deep RL frameworks. ``` procedure RUN-EPISODE(environment, agent, max_steps): state ← environment.RESET() # produces S_0 total_reward ← 0 t ← 0 while state is not TERMINAL and t < max_steps: action ← agent.SELECT-ACTION(state) # A_t ~ π(· | S_t) (next_state, reward, done) ← environment.STEP(action)

# environment computes R_{t+1}, S_{t+1} agent.OBSERVE(state, action, reward, next_state, done)

# agent may update π, value estimates, etc. total_reward ← total_reward + reward state ← next_state t ← t + 1 if done: break return total_reward, t # episode return and length ``` ``` procedure TRAIN(environment, agent, num_episodes): for episode in 1 .. num_episodes: (G, length) ← RUN-EPISODE(environment, agent, max_steps) record G, length for monitoring return agent ``` Two design points deserve emphasis because they are easy to misread on a first pass. First, `environment.STEP(action)` is the only place new information enters the system: the agent cannot query the environment's internal transition rule directly, it can only act and observe the consequence. This is why RL is described as learning from interaction rather than from a fixed dataset. Second, `agent.OBSERVE(...)` is deliberately left abstract: different algorithms (value-based, policy-gradient, model-based) use this experience tuple $(S_t, A_t, R_{t+1}, S_{t+1})$ in very different ways, but they all consume exactly this tuple, no more and no less. This is the common interface that lets the same environment be paired with radically different learning algorithms.

Framed purely as a protocol, the agent-environment loop has no "complexity" in the algorithmic sense of a sorting or search routine — it is a specification of an interface, not an algorithm that solves a problem. What we can analyze honestly is the per-step cost of running the loop, and the soundness of the framing, i.e. why this loop is an adequate model of sequential decision-making.

Per-step cost. Each iteration of `RUN-EPISODE` performs exactly one call to `agent.SELECT-ACTION`, one call to `environment.STEP`, and one call to `agent.OBSERVE`. If these calls run in $O(f)$, $O(g)$, and $O(h)$ time respectively (where $f, g, h$ depend on the specific policy representation, environment simulator, and learning update used), then one loop iteration costs $O(f + g + h)$, and an episode of length $T$ costs $O(T \cdot (f+g+h))$. For a tabular policy over a small discrete state-action space, $f$ and $h$ are $O(1)$ (array lookups/updates); for a deep-RL agent, $f$ and $h$ involve a forward and/or backward pass through a neural network, costing time proportional to the number of network parameters. The environment step cost $g$ is entirely determined by the simulator or physical system and is outside the agent's control. Space cost is $O(1)$ per step if the agent discards old transitions immediately (as in pure online learning), or $O(N)$ if it stores the last $N$ transitions in a replay buffer, a pattern used by many deep-RL methods.

Correctness — in what sense is the loop "correct"? There is no theorem to prove about the loop itself; instead, correctness here means the loop faithfully and losslessly represents the information available to a sequential decision maker. Two invariants justify this: 1. Information invariant. At time $t$, everything the agent has ever observed is exactly the history $H_t = (S_0, A_0, R_1, S_1, A_1, R_2, \dots, S_t)$. The pseudocode enforces this by construction: `agent.SELECT-ACTION` is only ever given `state`, and any additional memory the agent wants (e.g. past states) must be explicitly stored inside the agent object, never smuggled in from the environment. This makes explicit exactly what "learning from experience" means: the agent's policy at time $t$ can be any function of $H_t$, but nothing more. 2. Causal invariant. The reward $R_{t+1}$ and next state $S_{t+1}$ are functions (possibly stochastic) only of $S_t$ and $A_t$ as realized at time $t$ — they cannot depend on future actions the agent has not yet taken. This rules out "cheating" loops where the environment reveals information from the future, and matches how physical and computational systems actually behave: cause precedes effect. Formally, the environment defines a (possibly unknown) joint distribution $p(s', r \mid s, a) = \Pr(S_{t+1}=s', R_{t+1}=r \mid S_t = s, A_t = a)$, and the loop is simply repeated sampling from this conditional distribution, driven by the agent's chosen actions.

Honest tradeoffs. The loop's generality is also its main limitation. Because it makes almost no assumptions about $p(s', r \mid s, a)$, the loop alone gives no algorithm for computing good actions — it only defines the data agents can use. Efficient learning requires additional structure, most commonly the Markov property (dynamics depend only on the current state, not full history), which is what allows compact value-function and policy representations rather than ones that must condition on ever-growing histories $H_t$. Without some such assumption, the state space of "possible histories" grows without bound, and no tractable algorithm exists in general; this is precisely the gap that the Markov Property article closes.

Consider a minimal but non-trivial environment: a $1 \times 5$ grid world, states labeled $0,1,2,3,4$, where the agent starts at state $2$ (the middle) and can move `LEFT` or `RIGHT`. State $0$ gives a reward of $+5$ and ends the episode; state $4$ gives a reward of $+1$ and ends the episode; all other transitions give reward $-1$ (a small cost for taking time). This is deliberately asymmetric — the left exit is worth more than the right exit, but is one step farther away — so the "obvious" shortest path is not automatically the best one, which is exactly the kind of subtlety cumulative-reward reasoning must resolve. Suppose the agent follows a fixed deterministic policy: always move `LEFT`. Trace the loop:

The episode length is $T = 3$ steps of environment interaction (two moves plus the terminal reward), and the total reward collected is $(-1) + (-1) + 5 = 3$. Now compare against always moving `RIGHT`:

Total reward here is $(-1) + (-1) + 1 = -1$. Even though both policies take the same number of steps, moving `LEFT` accumulates strictly more total reward, $3$ versus $-1$, because the left terminal reward outweighs the step costs. This is exactly why an RL agent cannot be greedy about immediate reward alone (both single steps here give $-1$, tying) — it must reason about the cumulative consequence of a whole action sequence, which is the motivation for the return, defined in the next stage of this material. Note also that nothing in the loop itself told the agent which policy is better; the loop only generated the trace. Discovering that `LEFT` is superior — and doing so without exhaustively trying every deterministic policy — is precisely the job of the value-function and control algorithms built on top of this loop.

The agent-environment loop as a formal object emerged from the confluence of animal learning psychology, optimal control theory, and computer science. Its modern textbook form is due most directly to Richard S. Sutton and Andrew G. Barto, whose synthesis of trial-and-error learning (rooted in psychology) with the mathematics of optimal control (rooted in engineering) gave reinforcement learning its unified vocabulary of states, actions, rewards, and policies.

The agent-environment loop is not an abstraction confined to textbooks; it is the literal software interface used across modern RL systems. The OpenAI Gym / Gymnasium API, arguably the most widely used RL benchmarking interface, implements exactly the `reset()` / `step(action)` pattern shown in the pseudocode above, and nearly every published RL algorithm is built to plug into that interface. DeepMind's AlphaGo and AlphaZero cast board-game play as this loop, with the board position as state, legal moves as actions, and win/loss as terminal reward. Autonomous vehicle stacks use variants of this loop in simulation to train and evaluate driving policies before any real-world deployment. Data center cooling systems, such as those reported by Google, treat sensor readings as state, fan/cooling adjustments as actions, and energy savings as reward. Recommendation systems at scale (video, e-commerce, ads) frame user sessions as episodes, recommended items as actions, and engagement signals as reward, learning policies entirely from this same interaction stream. In every one of these systems, whatever the learning algorithm — value-based, policy-gradient, model-based, or a hybrid — the underlying loop of observe-act-reward-observe is identical, which is exactly why understanding it precisely, independent of any specific algorithm, is the foundational step in reinforcement learning.

Ask the tutor: How does adding the Markov property to this loop change what algorithms can guarantee about optimal behavior?