The formal agent model
The lecture's agent-and-environment picture, written as maths. Runs of states and actions, an agent as a function, memory as see / next / action, and how to score an agent with utility.
Kind: toolkit (the maths of week 1).
Week: 1 (not on the slides; it is the book’s version of slides 17 to 21).
Book: Wooldridge 2.5 Abstract architectures, 2.6 How to tell an agent what to do.
Techniques on this page: runs and the state transformer, agents as functions (and counting them), state-based agents, expected utility, predicate tasks.
The problem it solves
Words like “an agent with memory” or “the agent’s objective” are slippery. This model makes them exact, so you can prove things: that a thermostat with memory can do something no memoryless agent can, or that one agent is better than another on average.
It also gives you precise phrases for exam answers (“a purely reactive agent is a function \(Ag: E \to Ac\)”), and it is the notation later weeks reuse: week 2’s deductive agents are see/next/action with a logical database as the state.
Words you’ll hear
| Symbol or word | Plain meaning |
|---|---|
| \(E\) | the set of environment states |
| \(Ac\) | the set of actions; \(\alpha\) is one action |
| run \(r\) | a history: state, action, state, action, … |
| \(\mathcal R^E\), \(\mathcal R^{Ac}\) | runs that end in a state, runs that end in an action |
| \(\tau\) (tau) | the state transformer: given a history ending in an action, the set of possible next states |
| \(Per\) | the set of percepts (what the agent can perceive) |
| \(I\) | the set of internal states (the agent’s memory) |
| \(u\) | a utility function: a score |
| \(\Psi\) (psi) | a yes/no test of whether a run succeeded |
| \(\arg\max\) | “the one that gives the biggest value” |
Technique 1: runs and the environment
Problem it solves: describes “what happened” precisely, including uncertainty.
A run interleaves states and actions:
\[r:\; e_0 \xrightarrow{\alpha_0} e_1 \xrightarrow{\alpha_1} e_2 \xrightarrow{\alpha_2} \cdots \xrightarrow{\alpha_{u-1}} e_u\]
The state transformer \(\tau: \mathcal R^{Ac} \to 2^E\) takes a run ending in an action and returns the set of states that could come next. (\(2^E\) just means “a subset of \(E\)”.) Two things follow:
- the environment is history-dependent: the whole run matters, not only the last state;
- it is non-deterministic: a set, not a single state. If \(\tau(r) = \emptyset\) the run is over.
An environment is the triple \(Env = \langle E, e_0, \tau \rangle\): the states, the start state, and the rule for what happens next.
Technique 2: agents as functions
Problem it solves: pins down “how an agent decides” and lets you count and compare agents.
- A standard agent maps a history to an action: \(Ag: \mathcal R^E \to Ac\). It can use everything it has seen.
- A purely reactive agent looks at the current state only: \(Ag: E \to Ac\).
\[Ag(e) = \begin{cases}\text{heater off} & \text{if } e = \text{temperature OK}\\ \text{heater on} & \text{otherwise}\end{cases}\]
Every reactive agent is also a standard agent (just ignore the history), but not the other way round. Two agents are behaviourally equivalent in \(Env\) if they produce the same set of runs.
Worked example: counting agents. A reactive agent picks one action for each state, so there are \(|Ac|^{|E|}\) of them.
With \(|E| = 2\) and \(|Ac| = 2\): \(2^2 = 4\) thermostats (always on, always off, the sensible one, the perverse one). With \(|E| = 3\), \(|Ac| = 2\): \(2^3 = 8\).
Technique 3: agents with state (see, next, action)
Problem it solves: gives the agent a memory, so it can tell apart situations that look the same.
| Function | Type | Plain meaning | Lecture dimension |
|---|---|---|---|
| \(see\) | \(E \to Per\) | what the sensors report | observe |
| \(next\) | \(I \times Per \to I\) | update memory with the new percept | remember |
| \(action\) | \(I \to Ac\) | choose from memory | decide |
The loop: start in \(i_0\); observe \(e\); update \(i \leftarrow next(i, see(e))\); do \(action(i)\); repeat.
Partial observability in symbols: if \(e \ne e'\) but \(see(e) = see(e')\), one percept can’t tell them apart. Only the internal state \(i\), built from earlier percepts, can.
Worked example: a thermostat that remembers. The sensor reads only cold or ok; whether the door is open is invisible. Goal: heat when cold, but raise an alarm after 3 cold readings in a row (the door is probably open).
- \(I = \{0, 1, 2, \dots\}\), the number of consecutive cold readings; \(i_0 = 0\).
- \(next(i, \text{cold}) = i + 1\); \(next(i, \text{ok}) = 0\).
- \(action(i)\) = alarm if \(i \ge 3\); heater on if \(i\) is 1 or 2; heater off if \(i = 0\).
Percepts cold, cold, ok, cold, cold, cold give states 1, 2, 0, 1, 2, 3 and actions on, on, off, on, on, alarm.
Why no reactive agent can do this: keep the door shut and the room cold. The state (cold, shut) occurs at step 1, which needs “heater on”, and at step 3, which needs “alarm”. A function \(E \to Ac\) must give the same action for the same state. Contradiction.
Wooldridge notes (p. 38) that state-based agents are no more powerful than standard agents: both can depend on the whole history. State is just a compact way to implement that.
Technique 4: expected utility
Problem it solves: “tell the agent what to achieve, not how”, and compare agents when outcomes are uncertain.
A utility can score states, \(u: E \to \mathbb R\) (simple but short-sighted), or whole runs, \(u: \mathcal R \to \mathbb R\). In Tileworld, \(u(r)\) = holes filled ÷ holes that appeared.
With \(P(r \mid Ag, Env)\) the chance of each run:
\[EU(Ag, Env) = \sum_{r \in \mathcal R(Ag, Env)} u(r)\, P(r \mid Ag, Env)\]
The optimal agent maximises it: \(Ag_{opt} = \arg\max_{Ag} EU(Ag, Env)\). The bounded optimal agent only searches the agents that can actually run on the machine. Neither definition tells you how to build the agent.
Worked example. From \(e_0\) the agent takes one action and the run ends.
| Agent | Action | Outcomes (probability, utility) |
|---|---|---|
| \(Ag_1\) | \(\alpha_0\) | \(e_1\) (0.4, 8), \(e_2\) (0.6, 2) |
| \(Ag_2\) | \(\alpha_1\) | \(e_3\) (0.9, 5), \(e_4\) (0.1, 1) |
- \(EU(Ag_1) = 0.4 \times 8 + 0.6 \times 2 = 3.2 + 1.2 = 4.4\)
- \(EU(Ag_2) = 0.9 \times 5 + 0.1 \times 1 = 4.5 + 0.1 = 4.6\)
\(Ag_2\) wins, even though \(Ag_1\) has the single best outcome. Expected utility weighs each outcome by how likely it is.
Longer runs: multiply the probabilities along the run. \(\alpha\) gives \(e_1\) with 0.5, then \(\beta\) gives \(e_3\) with 0.8: that run has probability \(0.5 \times 0.8 = 0.4\).
Technique 5: predicate tasks (success or failure)
Problem it solves: often you only care whether the task got done. Then utility is just 1 (success) or 0 (failure), written \(\Psi(r)\).
- Pessimistic success: every possible run succeeds.
- Optimistic success: at least one run succeeds.
- Probabilistic: \(P(\Psi \mid Ag, Env)\) = the total probability of the successful runs.
Two common kinds:
- Achievement task \(\langle Env, G \rangle\): reach some goal state in \(G\).
- Maintenance task \(\langle Env, B \rangle\): never enter a bad state in \(B\) (a reactor that must never melt down).
Worked example (continuing Technique 4). Goal set \(G = \{e_1, e_3\}\).
- \(Ag_1\): \(P(\Psi) = 0.4\). Pessimistically it fails (the \(e_2\) run); optimistically it succeeds.
- \(Ag_2\): \(P(\Psi) = 0.9\). Pessimistically fails (\(e_4\)); optimistically succeeds.
Synthesis (skim). An algorithm that builds an agent for a task is sound if every agent it returns succeeds, and complete if it finds one whenever one exists. Soundness matters more.
What to read in the book
| Section | Read? | Why |
|---|---|---|
| 2.5 Abstract architectures | Recommended | Runs, \(\tau\), standard and reactive agents, see/next/action. Not on the slides, but it gives you exact exam language |
| 2.6 How to tell an agent what to do | Recommended | Utility over states and runs, expected utility, optimal and bounded optimal agents, predicate tasks |
| “Synthesizing agents” (end of 2.6) | Skim | Sound vs complete |
Page numbers are the book’s; in the scanned PDF add 21.
Practice prompt
I'm studying CS5940 Intelligent Agents (Wooldridge, An Introduction to MultiAgent Systems, 2nd ed., sections 2.5 and 2.6). I want practice on THE FORMAL AGENT MODEL, worked by hand:
- runs, the state transformer tau (and why it returns a set of states), environments <E, e0, tau>
- standard agents (runs to actions) vs purely reactive agents (states to actions); counting reactive agents |Ac|^|E|
- state-based agents with see, next and action: trace a percept sequence to internal states and actions
- proving that a state-based agent can do a task no purely reactive agent can
- expected utility of agents over runs (multiply probabilities along multi-step runs), optimal and bounded optimal agents
- predicate tasks: achievement vs maintenance, pessimistic / optimistic / probabilistic success
- sound and complete synthesis
Please:
1. Use plain, everyday language and explain any symbol in one short sentence.
2. Give me ONE question at a time, easy first, then harder, with friendly numbers.
3. Wait for my answer, then mark it and show the full working step by step.
4. If I get it wrong, explain the mistake and give me a similar question.
5. Every 5 questions, summarise my strengths and what to practise.