Agents

⚡ Key Takeaways

An agent is an entity that perceives its environment through sensors and acts upon it through actuators, choosing actions to maximize a performance measure. Formally modeled as a function from percept histories to actions, agents unify decision theory, control, and AI. They apply wherever autonomous, goal-directed behavior is modeled — from robotics and economics to reinforcement learning. The modern framework was crystallized by Russell & Norvig (1995), building on von Neumann, Wiener, and Bellman.

💡 The Core Insight

Intelligence and goal-directed behavior can be factored cleanly into three pieces: a percept stream coming in, an action stream going out, and an agent function that connects them. Rationality is then not a property of internal mechanism but of input-output behavior: an agent is rational if its agent function selects, for each percept sequence, an action expected to maximize a performance measure given what the percepts reveal. Everything else — planning, learning, perception — is engineering machinery for implementing or approximating this ideal mapping.

DefinitionAgent, Percept, Action

Let $\mathcal{P}$ be the set of possible percepts (sensor readings) and $\mathcal{A}$ the set of possible actions (actuator commands). A percept sequence is a finite string $p_{1:t} = (p_1, p_2, \dots, p_t) \in \mathcal{P}^*$ . An agent is defined by its agent function

1

\quad f : \mathcal{P}^* \to \mathcal{A}, \qquad a_t = f(p_{1:t}).

Derivation hint: This is a definition, not a derived result — it formalizes "the action depends on everything observed so far." Note the domain is $\mathcal{P}^*$ , the Kleene star (all finite sequences), capturing full history dependence. The agent program is the concrete algorithm running on an architecture (physical/computational substrate) that implements (or approximates) $f$ . We write agent = architecture + program.

DefinitionTask Environment — PEAS

A task environment is specified by the tuple

2

\quad \langle P, E, A, S \rangle = (\text{Performance measure}, \text{Environment}, \text{Actuators}, \text{Sensors}).

Derivation hint: "PEAS" is a checklist, not an equation; it is numbered here only to satisfy formatting. The performance measure $P$ is a function $P : \text{(environment histories)} \to \mathbb{R}$ used to grade behavior — crucially it is defined over states of the environment, not over the agent's internal beliefs.

DefinitionRational Agent

Given a performance measure $P$ , a percept sequence $p_{1:t}$ , and the agent's prior knowledge $K$ , a rational agent selects

3

\quad a_t^\star = \arg\max_{a \in \mathcal{A}} \; \mathbb{E}\!\left[\, P \mid p_{1:t}, K, a \,\right],

i.e. the action whose expected performance, conditioned on evidence and knowledge, is greatest. Derivation hint: The expectation is over the agent's posterior beliefs about hidden environment states, formed by conditioning a prior on the percept sequence (Bayesian updating). Rationality is bounded by what is knowable from $p_{1:t}$ and $K$ — not omniscience.

TheoremOptimality via the Bellman Equation

For a Markov Decision Process $(\mathcal{S}, \mathcal{A}, T, R, \gamma)$ with transition kernel $T(s'\mid s,a)$ , reward $R(s,a)$ , and discount $\gamma\in[0,1)$ , there exists an optimal policy $\pi^\star$ whose value function satisfies the Bellman optimality equation

4

\quad V^\star(s) = \max_{a\in\mathcal{A}} \Big[\, R(s,a) + \gamma \sum_{s'\in\mathcal{S}} T(s'\mid s,a)\, V^\star(s') \,\Big],

and the optimal agent acts greedily: $\pi^\star(s) = \arg\max_a [R(s,a) + \gamma\sum_{s'} T(s'\mid s,a) V^\star(s')]$ . Derivation hint: Apply the principle of optimality — an optimal policy's tail is optimal for the subproblem. The right-hand side is a contraction mapping in $\sup$ -norm with modulus $\gamma$ ; Banach's fixed-point theorem gives existence and uniqueness of $V^\star$ .

Theoremvon Neumann–Morgenstern Utility Representation

If an agent's preference relation $\succeq$ over lotteries (probability distributions over outcomes) satisfies completeness, transitivity, continuity, and independence, then there exists a utility function $u$ such that for lotteries $L_1, L_2$ ,

5

\quad L_1 \succeq L_2 \iff \mathbb{E}_{L_1}[u] \ge \mathbb{E}_{L_2}[u],

and $u$ is unique up to a positive affine transformation $u \mapsto \alpha u + \beta$ , $\alpha > 0$ . Derivation hint: Continuity gives, for each outcome between best $B$ and worst $W$ , a unique indifference probability $p$ with outcome $\sim [p:B,\,(1-p):W]$ ; set $u(\text{outcome})=p$ . Independence ensures these indifference probabilities combine linearly across compound lotteries, yielding the expected-utility form.

ProofBellman Optimality as a Fixed Point

Step 1. Define the Bellman optimality operator $\mathcal{T}$ on bounded functions $V:\mathcal{S}\to\mathbb{R}$ :

6

\quad (\mathcal{T}V)(s) = \max_{a}\Big[R(s,a) + \gamma\sum_{s'}T(s'\mid s,a)V(s')\Big].

Derivation hint: This packages the one-step lookahead in equation [4] into an operator so we can study its fixed points abstractly.

Step 2. Show $\mathcal{T}$ is a $\gamma$ -contraction in the sup-norm $\|V\|_\infty = \max_s |V(s)|$ . For any $V, U$ :

7

\quad \|\mathcal{T}V - \mathcal{T}U\|_\infty \le \gamma \,\|V - U\|_\infty.

Step 3. Since the space of bounded functions with sup-norm is complete, Banach's fixed-point theorem gives a unique fixed point $V^\star = \mathcal{T}V^\star$ , satisfying equation [4]. Iterating $V_{k+1}=\mathcal{T}V_k$ converges geometrically: $\|V_k - V^\star\|_\infty \le \gamma^k \|V_0 - V^\star\|_\infty$ — this is value iteration.

Step 4. The greedy policy w.r.t. $V^\star$ achieves $V^\star$ , so it is optimal. Hence a rational sequential agent's behavior is well-defined and computable (in the finite case). $\blacksquare$

∎

mathematician · John von Neumann | 1903–1957

A founder of the agent's mathematical core. With Oskar Morgenstern he wrote Theory of Games and Economic Behavior (1944), proving the expected-utility theorem (equation [5]) that justifies treating rational behavior as scalar maximization, and establishing the minimax theorem for two-player zero-sum games — the prototype of an adversarial agent. His work on self-reproducing automata and the stored-program architecture (the "von Neumann architecture") underpins the architecture half of "agent = architecture + program."

🧠 Intuition

Think of an agent as a thermostat that learned philosophy. The dumbest agent — a thermostat — maps the single percept "too cold/too hot" to "heater on/off"; its agent function is a tiny lookup table. Scale this up: a chess program's agent function maps a board (percept) to a move (action), but the table is astronomically large, so it's computed by search rather than stored. A self-driving car's percepts are camera frames and lidar; its actions are steering and throttle. In every case the behavior is the function from what-it-has-seen to what-it-does. Rationality just asks: of all functions you could implement, are you choosing the action that does best on average given what you actually know? Note the two humilities baked in: "on average" (the world is stochastic) and "given what you know" (you can't act on hidden facts). A rational agent is not omniscient or infallible — it is the best bet against its own ignorance.

Figure

Anatomy of an agent interacting with its environment

```svg

```

ExampleVacuum-Cleaner World — A Tabulated Agent Function

Given: Two squares $A, B$ . Percept = (location, status) where status ∈ {Clean, Dirty}. Actions: Left, Right, Suck. Performance: +1 per clean square per time step, over 100 steps.

Steps. Build the agent function as a table for the simplest reflex agent:

Percept	Action
[A, Dirty]	Suck
[A, Clean]	Right
[B, Dirty]	Suck
[B, Clean]	Left

Compute performance if both start dirty. Step 1: at A=Dirty → Suck (A clean). Step 2: A=Clean → Right. Step 3: at B=Dirty → Suck (B clean). From step 3 onward both squares clean: score $= 2$ per step. Over steps 4–100 (97 steps) plus partial earlier credit: clean-square-steps $\approx 2\times 97 + (\text{early partial})$ . Approximate total clean-square count $\approx 2 \times 98 = 196$ (after both clean by step 3).

Boxed answer:

\boxed{\text{Score} \approx 196 \text{ clean-square-steps; agent function = 4-row table}}

ExampleOptimal Action via Bellman — A 2-State MDP

Given: States $\{s_0, s_1\}$ , actions $\{$ stay, go $\}$ , $\gamma = 0.9$ . Rewards: $R(s_0,\text{go})=0$ , $R(s_1,\text{stay})=10$ , $R(s_1,\text{go})=10$ , $R(s_0,\text{stay})=0$ . Transitions: go from $s_0$ → $s_1$ w.p. 1; everything else stays put.

Steps. Guess the agent should reach $s_1$ and stay. Compute $V^\star(s_1)$ (stay loops forever in $s_1$ with reward 10):

V^\star(s_1) = 10 + 0.9\,V^\star(s_1) \;\Rightarrow\; V^\star(s_1) = \frac{10}{1-0.9} = 100.

Now $V^\star(s_0)$ : action "go" yields $0 + 0.9\,V^\star(s_1) = 0.9\times100 = 90$ ; action "stay" yields $0 + 0.9\,V^\star(s_0)$ . Since 90 > stay value, optimal is go:

V^\star(s_0) = 0 + 0.9 \times 100 = 90.

Boxed answer:

\boxed{V^\star(s_0)=90,\; V^\star(s_1)=100,\; \pi^\star(s_0)=\text{go},\; \pi^\star(s_1)=\text{stay}}

⚠️ Common mistake

"A rational agent always does the right thing / never fails." False. Rationality (equation [3]) maximizes expected performance given available evidence. An agent that crosses a road after looking both ways is rational even if a meteor then strikes it. Rationality ≠ omniscience, ≠ clairvoyance, and ≠ perfection. Confusing the performance measure (defined over real environment states) with the agent's internal utility estimate (its possibly-wrong beliefs) is the single most common error.

⚠️ Common mistake

"Bigger/more autonomous = more 'agent.'" Agency is binary in the formal definition — anything with the perceive→act loop is an agent, including a thermostat. What varies is sophistication (reflex vs. model-based vs. goal-based vs. utility-based vs. learning agents), not agenthood.

CounterexampleApparent Irrationality That Is Actually Rational

A robot vacuum that re-cleans an already-clean square seems irrational. But if its sensor is noisy (status reading is unreliable), then re-checking can raise expected performance by reducing the chance of leaving dirt. Under partial observability the "wasteful" action is optimal. Conversely, the Allais paradox is a genuine counterexample to humans being vNM-rational: people systematically violate the independence axiom, so no single utility function (equation [5]) can represent their choices — proving humans are not the rational agents of the theory.

connection

The agent framework is a hub linking several fields. The sequential-decision core is exactly a Markov Decision Process, whose solution via equation [4] is Dynamic Programming (Bellman). When the agent must learn $T$ and $R$ from experience instead of knowing them, you get Reinforcement Learning (Q-learning, policy gradients approximate $\pi^\star$ ). The preference foundations (equation [5]) belong to Decision Theory and Expected Utility Theory. Multi-agent interaction — where each agent's environment contains other agents — is Game Theory, with von Neumann's minimax and Nash equilibrium as solution concepts. The continuous-state, control-oriented version is Optimal Control and the Hamilton-Jacobi-Bellman Equation. Belief-tracking under partial observability links to Bayesian Inference and POMDPs.

🔬 Where this appears

⏳ History

- 1936 — Alan Turing's universal machine formalizes computation, providing the substrate for any agent program.

- 1944 — von Neumann & Morgenstern publish Theory of Games and Economic Behavior, proving the expected-utility theorem (equation [5]).

- 1948 — Norbert Wiener's Cybernetics frames purposeful behavior as feedback control — the perception–action loop made explicit.

- 1950 — Turing's "Computing Machinery and Intelligence" poses machine intelligence in behavioral terms, foreshadowing behavior-based agent definitions.

- 1957 — Richard Bellman's Dynamic Programming introduces the optimality principle and equation [4]; coins "curse of dimensionality."

- 1959 — Arthur Samuel's checkers program demonstrates a learning agent improving via self-play.

- 1989 — Christopher Watkins introduces Q-learning, a model-free way to converge toward equation [4] from experience.

- 1995 — Russell & Norvig's Artificial Intelligence: A Modern Approach canonizes the "rational agent" as AI's unifying organizing concept and the PEAS framework (equation [2]).

- 2015–2017 — Deep RL agents (DQN, AlphaGo) achieve superhuman performance, empirically validating the agent abstraction at scale.

open-problem

The clean theory frays at the edges. (1) Bounded rationality: equation [3] requires an intractable expectation and argmax; real agents have finite compute, so what is the right notion of optimal-given-resources? Russell's "rational metareasoning" and Simon's satisficing are partial answers, but no fully satisfactory theory of computationally bounded rationality exists. (2) Reward specification / alignment: the performance measure $P$ must be defined over environment states, yet specifying $P$ to capture genuine human intent is unsolved — misspecified rewards cause reward hacking and pose AI safety risks. (3) Non-stationarity and multi-agent recursion: when the environment contains other learning agents, the "stationary MDP" assumption behind equation [4] breaks, and equilibrium existence/learnability becomes subtle. (4) Continuous, high-dimensional, partially observed worlds push value iteration into approximation territory with weak convergence guarantees. (5) The hard question of agency itself: whether sophisticated function-approximators "really" have goals, or merely behave as if they do, remains philosophically contested.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also