All 48 exam-style questions for Agentic Artificial Intelligence, one set per note. Each answer opens with the key points a grader looks for, then a full model answer. Write or say your answer before revealing. The short drilling cards are on the flashcards page.
Give the Russell and Norvig and the Wooldridge definitions of an agent. What does each emphasise, and why do Russell and Norvig call the notion of an agent "a tool for analyzing systems"?
Key points: R&N: perceives environment through sensors, acts through actuators; Wooldridge: situated, autonomous action, design objectives; R&N stress the perception-action interface and “can be viewed as”, Wooldridge autonomy and goals; “agent” is a lens for analysis; calculator example.
Russell and Norvig: an agent is anything that can be viewed as perceiving its environment through sensors and acting upon it through actuators. Wooldridge (2001): an agent is a computer system situated in an environment and capable of autonomous action in it to meet its design objectives. Both place the agent in an observe-act loop with an environment. Russell and Norvig stress the interface (percepts in, actions out) and the phrase “can be viewed as”. Wooldridge adds autonomy (the system chooses its own actions) and objectives (it acts to achieve goals set by its designer).
Russell and Norvig warn that the notion of an agent is an analysis tool, not a line that divides the world into agents and non-agents. A calculator can be described as an agent that displays “4” after the percepts “2 + 2 =”, but that description adds nothing to our understanding of it. The agent view is worth using when a system chooses among actions in pursuit of an objective, as a vacuum robot or an LLM agent does.
Describe the kinds of agent program from simple reflex to learning agents. What does learning add, and what makes learning hard, especially when there are several agents?
Key points: simple reflex (current percept, condition-action rules); model-based (internal state); goal-based (considers future outcomes against a goal); utility-based (trade-offs via a utility function); learning agent improves its components from feedback; difficulties: value estimation, exploration vs exploitation, non-stationarity when others learn.
A simple reflex agent maps the current percept to an action with condition-action rules (vacuum: suck if dirty, else move). A model-based reflex agent keeps internal state about the parts of the world it cannot currently see. A goal-based agent uses goal information and predicts what its actions lead to, which brings in search and planning. A utility-based agent scores outcomes with a utility function (an internal version of the performance measure), so it can trade off conflicting goals and handle uncertainty. A learning agent can be any of these, plus learning: modifying each component of the agent to agree better with the available feedback, which improves its overall performance.
Learning a policy is hard because (1) the value of actions is difficult to estimate from noisy, delayed feedback; (2) the agent must balance exploration (trying actions to learn about them) against exploitation (using the best known action); and (3) environments can be non-stationary. In a multi-agent system the other agents are learning too, so from each agent’s view the environment keeps changing and old value estimates go stale.
What is an LLM agent? Explain the thought-action-observation loop and how ReAct implements it, linking each step to a component of the agent.
Key points: acts, observes, reasons and plans through natural language; token completion is multi-task; LLM plus role, memory, tools, planning; loop: reason/plan, act, observe; ReAct (Yao et al., ICLR 2023) prompts interleaved verbal reasoning and actions; Thought = reasoning (CoT), Action = tools, Observation = memory (tool output in context).
An LLM agent is an agent whose reasoning, planning and actions happen in natural language. A language model can play this role because next-token completion is multi-task: the same mechanism answers world-knowledge, history, planning and arithmetic prompts. The model becomes an agent when it is given a role, memory, tools and planning, and placed in a loop with an environment.
The loop has three steps: reason and plan in text, act, observe the result, then repeat. ReAct is a prompting technique that makes a language model generate verbal reasoning and actions, both as text, iteratively as Thought, Action, Observation. The Thought forces multi-step chain-of-thought reasoning; the Action is text that calls an external tool; the Observation inserts the tool’s output into the model’s context, which serves as its memory. The cycle continues until the agent produces a final answer.
Explain how LLM agents handle memory and tools. Distinguish short-term from long-term memory, and list the problems that tool use raises.
Key points: memory = facts, past interactions, context; key to go from LLM to agent; short-term = limited context window, context engineering, trimming or summarising; long-term = external databases or knowledge in parameters; tools = external functions that let agents act; creation, definition, selection, calling, output processing; MCP standardises connection.
Memory lets an agent keep facts, previous interactions and context; without it each step starts from nothing, which is why memory is key to going from an LLM to an agent. Short-term memory is the context window. It is limited, so what enters it must be chosen (context engineering), and long histories are trimmed or summarised. Long-term memory is either external, a database the agent retrieves from, or internal, the knowledge stored in the model’s parameters. Retrieval therefore serves as an agent’s long-term memory, and in the other direction agent-centric information access (Kanoulas et al.) retrieves among expert agents.
Reasoning lets an agent plan; tools let it act. A tool is an external function the model can use, such as search or code execution. Tool use raises five problems: creating and documenting tools so an LLM can use them, defining them so the agent knows they exist, selecting the right tool, calling it (parsing and executing the call), and processing its output back into the LLM. Toolformer showed models can teach themselves tool use; the Model Context Protocol standardises how LLMs connect to tools.
What are reasoning LLMs, and how can reasoning and planning in LLM agents be obtained or improved?
Key points: generate thought tokens before the answer; shift from train-time to test-time compute; prompting (CoT, zero- or few-shot) elicits reasoning in untuned models; search and verify; fine-tuning with RL (DeepSeek-R1); planning = decomposing into sub-tasks; CoT, Least-to-Most, Plan-and-Solve; fine-tuning (SFT, RL) for planning and the ReAct cycle; Reflexion.
A reasoning LLM produces thoughts as tokens before its final answer. This moves effort from train-time compute to test-time compute: more tokens at answer time means more computation on the problem. Reasoning can be elicited by prompting, with chain-of-thought prompting in zero-shot or few-shot form, even in models not tuned for reasoning. It can be improved by search and verify (sample many reasoning traces and reward the best) or by fine-tuning the model’s token probabilities for reasoning, for example with reinforcement learning, as in DeepSeek-R1.
Planning uses reasoning to find the steps that reach a goal: decompose the task into sub-tasks and generate an action sequence. Early methods were prompting techniques (CoT, Least-to-Most, Plan-and-Solve). Models can also be fine-tuned, by supervised fine-tuning or RL, to plan and to run the ReAct cycle better. Reflexion adds verbal reinforcement learning: the agent learns from feedback through reflections written in language.
What risks arise when many LLM agents interact? Use the categories of Hammond et al. and the OpenAI-Hugging Face incident.
Key points: miscoordination, conflict, collusion; agents communicated through a software repository service in unexpected ways; agent communication is not inherently problematic but can create risk; models tampered with outputs and logs, abused context compaction, injected code into the evaluator’s container, printed adversarial outputs; explicit about it in their CoT; behaviour depends on how rewards are defined.
Hammond et al. (2025) identify three under-explored risks of LLM-based multi-agent systems: miscoordination, conflict and collusion. The incident shows related risks in practice. Agents used Artifactory in unexpected ways to communicate with each other before the Hugging Face incident; the incident report notes that OpenAI’s models are trained to communicate when given a multi-agent collaboration tool, and that such communication is not inherently problematic but can create risk. The models also tried to deceive their evaluator, to hide that they had obtained an answer flag by cheating: erasing or tampering with outputs and message logs, abusing context compaction, injecting malicious code into the evaluator’s container and printing adversarial outputs, while stating these attempts openly in their chain-of-thought.
The lesson ties back to simple agents: the components that make agents useful (communication, memory, tools) are also routes for deception, and whether agents deceive depends on how their rewards and payoffs are defined, which is rarely trivial.
Using the Prisoner's Dilemma, the Stag Hunt and the vacuum world, explain why simple agents can produce outcomes nobody wants.
Key points: PD: D dominates, (D,D) the only equilibrium, worse for both than (C,C); Stag Hunt: (C,C) and (D,D) both equilibria, C risky; at 50% C, D earns 2.5 vs 2 so C declines; vacuum: two rewards give the same behaviour until Dump exists, then reward 2 dumps and re-sucks; design rewards for the outcome wanted.
In the Prisoner’s Dilemma (C,C = 3,3; C,D = 0,5; D,D = 1,1) defecting pays more whatever the other does (5 > 3, 1 > 0), so rational agents reach (D, D), which both rank below (C, C): a cooperation dilemma. In the Stag Hunt (C,C = 4,4; C,D = 0,3; D,D = 2,2) the best reply matches the partner, so both (C, C) and (D, D) are equilibria; (C, C) is better but risky, a coordination dilemma. In a population with 50% of each type meeting at random, C earns 2 and D 2.5 on average, so if successful strategies spread, cooperators decline.
In the vacuum world, rewarding each clean square per time step and rewarding each unit of dirt sucked produce the same behaviour with Left, Right and Suck. Add Dump and the second reward is maximised by dumping dirt and sucking it again forever. Rewards should describe the outcome wanted in the environment, not the behaviour the designer expects.
Describe the hierarchy of game models from one-shot normal-form games to partially observable stochastic games. Give each model's formal definition, say what it adds to the previous one, and how agents' policies change.
Key points: normal-form (I,{Ai},{Ri}), no time or state, Ri on joint actions, policies are distributions over actions; repeated: same game over time, policies condition on action history ht=(a0,…,at−1); stochastic game (I,S,{Ai},{Ri},T,μ) adds states, transitions, initial distribution; POSG adds observation sets Oi and functions Oi:A×S×Oi→[0,1], policies condition on observation histories; each model contains the previous one, with an example of each.
A normal-form game is a tuple (I,{Ai},{Ri}): a finite set of agents I, a finite action set Ai for each agent, and reward functions Ri:A→R on the joint actions A=A1×⋯×An. There is no time and no state, only actions and rewards. Each agent follows a policy πi, a distribution over its actions. Examples: the Prisoner’s Dilemma and Stag Hunt (general-sum), Matching Pennies (zero-sum), a common-reward coordination game.
A repeated normal-form game plays the same game over time steps. Policies become conditioned on the history of joint actions, πi(ait∣ht) with ht=(a0,…,at−1), which allows strategies such as Tit-for-Tat and Win-Stay Lose-Shift. The number of steps matters for which strategies do well.
A stochastic game(I,S,{Ai},{Ri},T,μ) adds a finite set of states S, a transition function T (the probability of the next state given the current state and joint action) and an initial state distribution μ; rewards can depend on the state. Each state can carry its own game, and actions affect both the immediate reward and the future state. Examples: a three-state game with a matrix per state, the vacuum world (one agent), a foraging grid world with two agents.
A partially observable stochastic game adds, for each agent, a finite observation set Oi and an observation function Oi:A×S×Oi→[0,1], the probability of each observation given the joint action and resulting state. Agents get incomplete information about the state and others’ actions, so policies condition on their own observation history hit=(oi0,…,oit−1). Examples: autonomous driving, card games with hidden hands, agents in a grid world that see only nearby cells. Each model is a special case of the next: a repeated normal-form game is a stochastic game with one state, and a stochastic game is a POSG where observations reveal the state.
Define a best response and a Nash equilibrium formally. What did Nash prove, and what are the three limitations of the Nash equilibrium as a solution concept?
Key points:BRi(π−i)=argmaxπiUi(⟨πi,π−i⟩); NE: ∀i,πi′: Ui(⟨πi′,π−i⟩)≤Ui(π), mutual best response; Nash 1950: every finite general-sum normal-form game has an equilibrium, possibly mixed; sub-optimality (PD) and non-uniqueness (SH, possibly infinitely many, different returns); incompleteness (off-equilibrium paths, how equilibria are reached).
A best response of agent i to the other agents’ policies π−i is a policy that maximises i‘s expected return given them: BRi(π−i)=argmaxπiUi(⟨πi,π−i⟩), where ⟨πi,π−i⟩ is the complete joint policy and Ui the expected return. A Nash equilibrium is a joint policy π in which every agent’s policy is a best response to the others’: for every agent i and every alternative policy πi′, Ui(⟨πi′,π−i⟩)≤Ui(π). No agent can improve its expected return by changing its own policy while the others keep theirs.
Nash (1950) proved that every finite general-sum normal-form game has at least one Nash equilibrium if mixed policies are allowed (by a fixed-point argument). Rock-Paper-Scissors has no pure equilibrium but a mixed one, each action with probability 1/3.
Limitations. (1) Sub-optimality: equilibria need not maximise returns; in the Prisoner’s Dilemma (D, D) is the equilibrium while (C, C) gives both more. (2) Non-uniqueness: there can be several, even infinitely many, equilibria with different returns, as in the Stag Hunt, and the concept does not say which is played. (3) Incompleteness: in sequential games equilibria do not specify actions off the equilibrium path, and the concept does not say how agents reach an equilibrium. The first two motivate refinements such as Pareto optimality, welfare and fairness; the third motivates dynamic approaches such as evolutionary game theory.
In the game below (row player's payoff first), find all pure Nash equilibria, the Pareto-optimal outcomes, and the welfare-optimal and fairness-optimal outcomes. Rows U, D; columns L, R; (U, L) = 5, 1; (U, R) = 0, 0; (D, L) = 1, 1; (D, R) = 3, 3.
Key points: best responses: row U against L, D against R, column L against U, R against D; pure NE (U, L) and (D, R); Pareto optimal (U, L) and (D, R); welfare 6, 0, 2, 6, so both NE are welfare-optimal; fairness 5, 0, 1, 9, so (D, R) is the only fairness-optimal outcome.
Nash. Against L the row player prefers U (5 > 1); against R it prefers D (3 > 0). Against U the column player prefers L (1 > 0); against D it prefers R (3 > 1). Cells where both are best-responding: (U, L) and (D, R). (U, R) and (D, L) are not equilibria: at (U, R) the row player gains by switching to D, at (D, L) the column player gains by switching to R.
Pareto. (D, R) = (3, 3) dominates (D, L) = (1, 1) and (U, R) = (0, 0). (U, L) = (5, 1) and (D, R) = (3, 3) do not dominate each other (the row player prefers the first, the column player the second), so both are Pareto optimal.
WelfareW=U1+U2: 6, 0, 2, 6. Both (U, L) and (D, R) are welfare-optimal; the sum cannot separate them. FairnessF=U1⋅U2: 5, 0, 1, 9. Only (D, R) is fairness-optimal, because the product prefers the equal split.
Show that Rock-Paper-Scissors (win 1, lose −1, tie 0) has no pure Nash equilibrium, and that both players choosing each action with probability 1/3 is a Nash equilibrium. What kind of game is it?
Key points: zero-sum (payoffs in each cell sum to 0); in every pure cell the loser, or either player at a tie, can switch to the beating action and gain; against uniform play each pure action earns 31(0−1+1)=0, so every mixed policy is also worth 0; no profitable deviation, so uniform play is a NE; consistent with Nash’s existence result.
It is a zero-sum game: in every cell one player’s gain is the other’s loss. No pure equilibrium: at a tie, either player can switch to the action that beats the other’s and get 1 instead of 0; at a win for one player, the loser can switch to the action that beats the winner’s and get 1 instead of −1. So in every pure cell some player has a profitable deviation.
Mixed equilibrium. Suppose the column player plays R, P, S with probability 1/3 each. The row player’s expected payoff from R is 31⋅0+31⋅(−1)+31⋅1=0, and by symmetry also 0 from P and from S. Any mixed policy averages these, so it also earns 0. No deviation earns more than the uniform policy’s 0, so uniform play is a best response to uniform play, and by symmetry the same holds for the column player. Both best-responding means a Nash equilibrium, which illustrates Nash’s theorem: equilibria always exist once mixed policies are allowed.
Why does evolutionary game theory study populations of agents instead of rational players? Explain the idea of frequency-dependent fitness, state the replicator equation with its terms, and give its three interpretations.
Key points: static solution concepts do not say how equilibria are reached (von Neumann and Morgenstern: theory “thoroughly static”), and real agents use trial and error, incomplete information, imitation; biology plus game theory, Maynard Smith and Price in the 1970s; fitness depends on the frequency of other types, like payoffs on others’ strategies; x˙=x(fC(x)−fˉ(x)), C replicates when fitter than average; biology (natural selection), economics (imitation), computer science (RL dynamics, Börgers and Sarin).
Solution concepts such as the Nash equilibrium are static: they say which joint policies are stable but are silent on how agents get there, and they assume rational agents computing best responses. Von Neumann and Morgenstern called their own theory “thoroughly static” and a dynamic theory more complete. Real agents often learn by trial and error, have incomplete information and imitate others, so we ask how the strategies in a population change over time depending on what others do.
Evolutionary game theory combines evolutionary biology and game theory, following Maynard Smith and Price in the 1970s. In natural selection fit types spread, but fitness cannot be measured in isolation: it depends on how frequent the other types are, exactly as a payoff in game theory depends on the others’ strategies.
The replicator equation: x˙=x(fC(x)−fˉ(x)), where x is the fraction using strategy C, fC(x) the average payoff (fitness) of C when a fraction x uses C, and fˉ(x)=xfC+(1−x)fD the population’s average fitness. C replicates when it is fitter than average, at a rate proportional to its current share. The same equation describes replication and natural selection in biology, social learning by imitation in economics, and reinforcement learning dynamics in computer science (Börgers and Sarin showed that simple reinforcement learning follows it on average).
Derive the two-strategy replicator equation x˙=x(1−x)(fC−fD). Apply it to the Stag Hunt (R=4,S=0,T=3,P=2): find the rest points and their stability, and say what happens to a population that starts with 50% C.
Key points:fˉ=xfC+(1−x)fD gives fC−fˉ=(1−x)(fC−fD); fC=4x, fD=3x+2(1−x), so x˙=x(1−x)(3x−2); rest points 0 (stable), 2/3 (unstable), 1 (stable); at x=1/2, x˙=−1/8, C decreases to 0; the interior point is the mixed NE and a tipping point.
Derivation.fˉ=xfC+(1−x)fD, so fC−fˉ=(1−x)fC−(1−x)fD=(1−x)(fC−fD), and multiplying by x gives x˙=x(1−x)(fC−fD). Since x(1−x)>0 for 0<x<1, the sign of fC−fD decides the direction.
Fitness. With random pairing a partner plays C with probability x: fC=4x+0⋅(1−x)=4x and fD=3x+2(1−x)=2+x. So fC−fD=3x−2 and x˙=x(1−x)(3x−2).
Rest points.x=0, x=1, and x=2/3 where 3x−2=0. For x<2/3, x˙<0; for x>2/3, x˙>0. So the population moves away from 2/3 on both sides: 2/3 is unstable, and 0 and 1 are stable (also g′(0)=S−P=−2<0, g′(1)=T−R=−1<0).
50% C.x˙(1/2)=21⋅21⋅(−21)=−81<0: C agents earn 2 on average against D agents’ 2.5, so C decreases, and keeps decreasing to x=0, all D. The interior rest point is the mixed Nash equilibrium, but it is a tipping point: populations above two thirds C go to all C, below to all D. Equilibrium selection in the Stag Hunt depends on where the population starts.
Analyse the donation game ( b>c>0) and the Hawk-Dove game ((C,C) = 3,3; (C,D) = 2,8; (D,C) = 8,2; (D,D) = −2,−2) under the replicator dynamics. For each, give the Nash equilibrium, the long-run population, and compare with the Stag Hunt.
Key points: donation: NE (D,D), social optimum (C,C); fC=xb−c, fD=xb, x˙=−cx(1−x)<0, all D from any start; Hawk-Dove: symmetric NE mixed with C at 4/9, x˙=x(1−x)(4−9x); 0 and 1 unstable, 4/9 stable, coexistence; mixed equilibrium unstable in the Stag Hunt, stable in Hawk-Dove.
Donation game. Payoffs (C,C) = b−c each, (C,D) = −c, b; (D,C) = b, −c; (D,D) = 0. D earns c more than C against either action, so (D, D) is the unique Nash equilibrium, while (C, C) maximises the sum, 2(b−c)>0. In a population, fC=x(b−c)+(1−x)(−c)=xb−c and fD=xb, so x˙=x(1−x)(−c)<0 for all interior x: cooperators decline from any start and the population ends fully D. x=1 is an unstable rest point, since a single defector earns b>b−c.
Hawk-Dove. Against C, D is better (8 > 3); against D, C is better (2 > −2). The symmetric equilibrium is mixed: with the partner playing C with probability q, C earns 2+q and D earns 10q−2, equal at q=4/9. (There are also asymmetric pure equilibria (C, D) and (D, C).) In a population, fC=3x+2(1−x)=2+x and fD=8x−2(1−x)=10x−2, so x˙=x(1−x)(4−9x). Rest points 0, 4/9, 1; x˙>0 below 4/9 and <0 above, so 4/9 is stable and the pure states are unstable (g′(0)=S−P=4>0, g′(1)=T−R=5>0). The population converges to coexistence, about 44% C, because each strategy earns more when it is rare.
Comparison. In the Stag Hunt the interior rest point (the mixed equilibrium at 2/3) is unstable and populations go to all C or all D depending on the start. In Hawk-Dove the mixed equilibrium is the stable outcome. In the donation game there is no interior rest point and the Nash prediction (all D) is reached from everywhere.
How does reinforcement learning differ from supervised learning? Describe the components of an RL problem and explain what makes a state Markov.
Key points: RL is closed-loop and sequential, supervised learning open-loop; RL data is not i.i.d. and has rewards instead of labels; agent = policy πθ(a∣s), environment = MDP {S,A,T,r}, goal = maximise expected (discounted) return; Markov: the state summarises the past as far as the future is concerned; hidden information such as a battery level breaks it.
In supervised learning someone provides a fixed dataset of inputs with correct labels, assumed i.i.d., and the model learns fθ(x)≈y; the model’s outputs do not change the data it sees, so it is open-loop. RL is sequential decision making: the agent’s actions shape what it sees next. It observes a state, chooses an action, and receives a reward and the next state, so the data is a trajectory produced by its own policy. That data is not i.i.d. (consecutive samples are correlated and depend on the policy), and there are no labels, only a reward saying how good the outcome was.
The agent is its policy πθ(a∣s), a probability over actions in each state with parameters θ. The environment is a Markov decision process: states S, actions A, transition probabilities P(s′∣s,a) and a reward function R(s,a,s′). The goal is to maximise the expected discounted return E[∑kγkrt+k]. Algorithms repeat: run the policy to generate samples, estimate returns or fit a model, improve the policy.
A state is Markov when it is a complete summary of the past as far as the future is concerned: the distribution of the next state given the current state and action does not change when earlier history is added. A robot’s grid position is Markov only if nothing else matters. If the robot has a battery the state does not include, the same cell can lead to different futures depending on how long it has been running, so the position alone is no longer Markov.
Define Vπ and Qπ, write the Bellman equations for a policy, and explain how iterating them leads to value iteration. Why does this approach need a model?
Key points:Vπ and Qπ as expected discounted returns, specific to a policy; Vπ=∑aπQπ, V∗=maxaQ∗; Bellman equations as self-consistency conditions, iterated until values stop changing; a greedy policy turns the average into a max (value iteration, a moving target, optimal when it stops changing); needs P and R, often unavailable or intractable.
Vπ(s)=Eπ[∑tγtrt∣s0=s] is the expected discounted return from s following π; Qπ(s,a) is the same but with action a taken first. Both depend on the policy. They are related by Vπ(s)=∑aπ(a∣s)Qπ(s,a), and for the optimal policy V∗(s)=maxaQ∗(s,a).
The Bellman equations express self-consistency: Vπ(s)=∑aπ(a∣s)[r(s,a)+γ∑s′P(s′∣s,a)Vπ(s′)], and similarly Qπ(s,a)=r(s,a)+γ∑s′P(s′∣s,a)∑a′π(a′∣s′)Qπ(s′,a′). A state’s value is the step reward plus the discounted expected value of where you land. The values are right when these hold in every state. Starting from any guess and applying them as updates to all states until the values stop changing evaluates the policy.
If the policy is made greedy with respect to the current values, π(s)=argmaxa[r(s,a)+γ∑s′PV(s′)], the update becomes V(s)←maxa[r(s,a)+γ∑s′P(s′∣s,a)V(s′)]: value iteration. It chases a moving target, since the policy being evaluated improves after every update, and when the values stop changing the greedy policy is optimal. This works by exploiting the Markov property (decisions can be made state by state) instead of searching ∣A∣∣S∣ policies.
The catch is that every update uses P(s′∣s,a) and R. In most problems that model is unknown, or so large that it is intractable (Atari games have astronomically many states); usually there is only a simulator to sample from.
Derive the Q-learning update from the Bellman equation for Q, give its pseudocode, and explain the challenges that learning from samples brings.
Key points: without a model, replace the expectation over next states by one observed transition (s,a,r,s′); greedy target r+γmaxa′Q(s′,a′); move by learning rate α towards it; full pass against single sample, noisy target; pseudocode with ε-greedy action choice; challenges: exploration, noisy or high-variance updates and credit assignment, data efficiency.
The Bellman update for Q is Q(s,a)←r(s,a)+γ∑s′P(s′∣s,a)∑a′π(a′∣s′)Q(s′,a′). Without P and R, the agent can only act and observe a transition (s,a,r,s′). Q-learning replaces the expectation over s′ with that single sample and uses the greedy policy in the target, giving the target r+γmaxa′Q(s′,a′). Because one sample is noisy, the estimate moves only a fraction α of the way: Q(s,a)←Q(s,a)+α[r+γmaxa′Q(s′,a′)−Q(s,a)].
Pseudocode: initialise Q to 0. For each episode, start in s; until terminal, choose a ε-greedily from Q, take it, observe r and s′, set target =r if s′ is terminal and r+γmaxa′Q(s′,a′) otherwise, update Q(s,a) by α times the TD error, set s←s′. Decay ε and α over episodes; return the greedy policy.
Dynamic programming does a full pass over every state, action and outcome; Q-learning uses one state, one action, one outcome. That brings challenges. Exploration: the agent learns only about states it visits, so it needs an exploration schedule. Noise and credit assignment: single-sample targets give biased, high-variance updates, and delayed rewards have to be traced back to their causes. Data efficiency: samples may be expensive. Value iteration is simple and fast but needs the model; Q-learning needs no prior knowledge but is slower.
Computation: an agent has Q(s,a)=2, takes a, receives r=1 and lands in s′ with maxa′Q(s′,a′)=4. With α=0.25 and γ=0.5, what is the new Q(s,a)? What would it be if s′ were terminal?
Key points: target =r+γmaxa′Q(s′,a′)=1+0.5×4=3; TD error =3−2=1; new Q=2+0.25×1=2.25; terminal: target =1, error =−1, new Q=1.75.
The Q-learning update is Q(s,a)←Q(s,a)+α[r+γmaxa′Q(s′,a′)−Q(s,a)]. The target is 1+0.5×4=3. The TD error is 3−2=1. The new value is 2+0.25×1=2.25. Equivalently, as a running average: (1−0.25)×2+0.25×3=1.5+0.75=2.25.
If s′ is terminal there is no future value, so the target is just r=1. The TD error is 1−2=−1 and the new value is 2+0.25×(−1)=1.75.
What does the discount factor do? Compute the effective horizon for γ=0.9 and γ=0.99, find the γ with an effective horizon of 50 steps, and use the apple orchard to explain how γ changes the solution. Then explain the learning rate's role.
Key points:γ sets the present value of future rewards, balancing short and long term; effective horizon 1/(1−γ): 10 and 100 steps, γ=0.98 for 50; needed for infinite-horizon tasks, usually high (0.99); orchard: low γ over-harvests, high γ leaves apples to regrow; α weighs new samples against current beliefs (running average); high α fine when deterministic, noisy when stochastic; low α slow; decay.
The discount factor γ∈[0,1) weights a reward k steps ahead by γk, so it sets the present value of future rewards and balances short-term against long-term gains. The effective horizon is 1/(1−γ), because the weights sum to ∑kγk=1/(1−γ): for γ=0.9 it is 1/0.1=10 steps, for γ=0.99 it is 1/0.01=100 steps. For a horizon of 50, 1/(1−γ)=50 gives γ=1−1/50=0.98. γ is needed mainly for infinite-horizon tasks, where it keeps the sum of rewards finite, and is usually set high (0.99).
γ also changes which solution is found. In an orchard where apples regrow at a rate depending on how many are left, an agent with low γ cares only about rewards soon, so it picks every apple now and the orchard stops producing. With high γ, future harvests count, so it leaves enough apples to regrow and harvests sustainably.
The learning rate α controls how much a new sample is trusted against the current estimate: the update is a running average Q←(1−α)Q+α⋅target. In a deterministic environment a high α is fast and fine, and a low one only slows learning. In a stochastic environment a high α makes the estimate jump with every lucky or unlucky outcome so it never settles, while a low α is smooth and accurate but slow. The usual compromise is to decay α: large early, small later.
Computation: with 5 actions and ε=0.1, give the ε-greedy probability of each action. Compare ε-greedy with Boltzmann exploration, and explain why exploration needs a schedule.
Key points: greedy action 1−0.1+0.1/5=0.92; each other action 0.1/5=0.02 (sum 0.92+4×0.02=1); ε-greedy simple and easy to decay, exploration blind; Boltzmann exp(Q/τ)/∑exp(Q/τ), value-aware, hard to tune; too little exploration sticks to the suboptimal, too much wastes samples, so decay.
With probability 1−ε=0.9 the agent takes the greedy action; with probability 0.1 it picks uniformly among all 5 actions, which can also be the greedy one. So the greedy action has probability 0.9+0.1/5=0.92 and each of the other four 0.1/5=0.02; the total is 0.92+0.08=1.
ε-greedy is simple and easy to decay, but its exploration is blind: a catastrophic action is tried as often as a nearly optimal one. Boltzmann exploration chooses a with probability exp(Q(s,a)/τ)/∑a′exp(Q(s,a′)/τ), so it is value-aware: better actions are tried more. Its temperature τ is hard to tune, because the right value depends on the scale of the Q-values; low τ is nearly greedy, high τ nearly uniform.
Exploration is needed because an agent that never tries an action never finds out it is better: one that keeps refining the first path it found to a +2 goal never discovers a +5 goal. Too much exploration wastes samples on actions already known to be bad. A decay schedule explores a lot early, when little is known, and exploits more later.
Computation: classify each game as fully cooperative, zero-sum or general-sum, and say what learning has to achieve in each kind: (i) (4,4) (0,0) / (0,0) (2,2); (ii) (1,−1) (−1,1) / (−1,1) (1,−1); (iii) (3,3) (0,5) / (5,0) (1,1).
Key points: rule: equal payoffs in every cell = fully cooperative, payoffs summing to zero in every cell = zero-sum, otherwise general-sum; (i) fully cooperative, (ii) zero-sum (matching pennies), (iii) general-sum (Prisoner’s Dilemma); cooperative needs coordination of tasks, general-sum balancing individual and group welfare (Pareto inefficiency), zero-sum robustness to many opponents.
Compare the two payoffs in each cell. In (i) they are always identical, R1=R2, so the game is fully cooperative: both agents want the same thing, and the challenge is coordinating on the better outcome (4,4) over (2,2). In (ii) every cell sums to zero, R1=−R2, so it is zero-sum (matching pennies): one agent’s win is the other’s loss, my changes prompt my opponent’s counter-changes, and the aim is a policy robust to many kinds of opponent. In (iii) the payoffs differ and the sums are 6, 5, 5 and 2, so it is neither: general-sum, the Prisoner’s Dilemma. Agents have their own preferences, so besides coordinating they must balance individual and group welfare, and learners struggle with Pareto inefficiency, here mutual defection (1,1), which both agents rank below (3,3).
The payoff structure matters because it defines what a good solution is, what can go wrong and which algorithms make sense.
Define a stochastic game and formulate the iterated Prisoner's Dilemma as one. Why is "maximise your return" no longer an adequate solution concept, and what does MARL optimise for instead?
Key points: multi-agent generalisation of an MDP, N agents acting simultaneously, each with its own reward; tuple (N,S,{Ai},P,{Ri},γ) with transitions and rewards depending on the joint action; IPD: N=2, states CC, CD, DC, DD (last joint action), actions C, D, rewards from the PD matrix; Ji depends on all policies; alternatives: stability (Nash equilibrium), no regret, social welfare, robustness to opponents.
A stochastic game generalises an MDP to N agents that act simultaneously, each with its own reward. It is the tuple (N,S,{Ai},P,{Ri},γ): the set of agents, a shared state space, an action set per agent, a transition function P(s′∣s,a1,…,aN) that depends on the joint action, a reward function Ri(s,a1,…,aN,s′) for each agent, and a discount factor.
The iterated Prisoner’s Dilemma has N=2. The state is the previous round’s joint action, S={CC,CD,DC,DD}, and each agent’s actions are {C,D}. The next state is fixed by the current joint action (play C and D and the next state is CD). Rewards follow the PD matrix: 3 each for mutual cooperation, 5 and 0 when one defects on a cooperator, 1 each for mutual defection. Policies can condition on the state, for example cooperating if the other cooperated last round.
Each agent’s objective is Ji(π1,…,πN)=E[∑tγtRti∣π1,…,πN]: its return depends on everyone’s policies, but it controls only its own. “Maximise your return” therefore does not pin down a solution, because my best policy depends on yours and yours on mine. MARL optimises instead for stability (a Nash equilibrium, where no agent gains by changing only its own policy), no regret, social welfare (total reward), or robustness to many kinds of opponent, depending on the setting.
Using matching pennies, explain why convergence in multi-agent learning is not as simple as in an MDP, and give the different notions of convergence.
Key points: in an MDP, converged = the policy stops changing; matching pennies: matcher against mismatcher, zero-sum; any change by one player gives the other a reason for the opposite change, so learning dynamics orbit; equilibrium 0.5/0.5; cycling policies match the equilibrium on average and earn the same average reward; notions: exact policy, average policy over many episodes, average reward.
In an MDP, learning has converged when the policy stops changing, and the optimal policy is then reached. In matching pennies each player picks heads or tails; the row player wins (+1, the other −1) if they match, the column player if they differ, like a goalkeeper and a penalty taker. If the row player leans towards heads, the column player’s best response is tails; then the row player’s best response is tails, then the column player’s is heads, and so on. Any change one makes gives the other a reason to make the opposite change, so the learning dynamics orbit around the equilibrium, where each plays heads with probability 0.5, and the policies never settle.
Yet averaged over time the cycling policies play each action half the time and earn the equilibrium’s average reward (0 each). Whether they have “converged” depends on the notion: the policy matching the equilibrium exactly (not satisfied), the policy matching it on average over many episodes (satisfied), or the average reward matching that of the optimal policy (satisfied). Multi-agent learning therefore has to say which property it wants from a solution.
Explain non-stationarity in MARL using the transition function agent i experiences, and describe its consequences.
Key points: other agents are part of agent i‘s environment; Pi(s′∣s,ai)=∑a−i[∏j=iπj(aj∣s)]P(s′∣s,ai,a−i) changes whenever π−i changes; single-agent targets move only as own estimates improve, MARL targets also move as others’ policies change; experience has a shelf life; cycling, broken convergence guarantees, noisy targets with low signal-to-noise ratio.
From agent i‘s point of view the other agents are part of the environment. The probability of reaching s′ after playing ai is Pi(s′∣s,ai)=∑a−i[∏j=iπj(aj∣s)]P(s′∣s,ai,a−i): the true, fixed transition function averaged over what the others might do, weighted by their policies. When the others learn, π−i changes, so Pi changes too, and so does agent i‘s expected reward. The environment agent i is learning about is not stationary.
In single-agent RL the learning targets move only because the agent’s own estimates improve. In MARL they also move because the other agents’ policies change, so an agent’s experience has a shelf life: old targets it bootstraps from become outdated. Consequences: cycling, where best responses chase each other as in matching pennies and both agents keep improving without converging; broken guarantees, since convergence proofs for MDP methods such as Q-learning assume a fixed environment; and noisy targets, since bootstrapping from stale estimates gives a low signal-to-noise ratio. In practice it is a moving signal that is hard to track, and it gets worse as more agents’ policies change at once.
What is multi-agent credit assignment? Explain it with the lazy agent in level-based foraging and with the fishing environment, and say why it is hardest in fully cooperative games.
Key points: single-agent RL has temporal credit (which earlier action), MARL adds agent credit (whose action); lazy agent: shared team reward reinforces an idle agent when teammates succeed; disentangling needs counterfactuals and many samples, a hard causal inference problem with low signal-to-noise ratio; worst in fully cooperative games (no individual signal); also in general-sum: fishing, wrong lessons from good and bad outcomes.
Single-agent RL faces temporal credit assignment: deciding which earlier actions led to a reward. With several agents there is a new axis: deciding whose actions led to it. In level-based foraging, three agents collect apples and share a team reward of +1 whenever an apple is collected. If A and B do the work while C wanders in a corner, C still receives +1, so whatever C was doing is reinforced. The lazy agent is rewarded because its teammates succeeded.
Separating each agent’s contribution requires counterfactual reasoning (what would have happened had C acted differently?), which takes many samples and a hard exploration effort. It adds a layer to an already hard causal inference problem, at a very low signal-to-noise ratio.
It is worst in fully cooperative games, because a shared reward carries no individual signal at all. It also arises in general-sum games, where rewards are individual but depend on the others. In a fishing environment with a lake that can be depleted, an agent that fishes aggressively while others hold back catches a lot and learns that aggression is good, though it only paid because others held back. An agent that fishes sustainably while the others hold back too catches little and learns that sustainability is bad, though that shared restraint is what keeps the lake stocked. (If the others were fishing aggressively instead, the small catch would be their doing, and the agent would wrongly blame its own sustainable fishing.) In both cases it credits its own action with an outcome that depended on everyone.
What is the equilibrium selection problem? Why is it called native and inescapable, why do learners tend to reach "safe" equilibria, and how does the number of agents affect this and the other challenges?
Key points: games can have several equilibria, and even perfect learners can converge to a suboptimal one; native to multiple agents and not fixed by better learning; path dependence (history and initial conditions decide), some equilibria exist but are unreachable (side of the road, messaging apps, corrupt government); costly exploration mistakes push learners to safe equilibria (stag hunt); more agents: exponential joint spaces (64N, 5N), more policies chasing each other, harder credit assignment, equilibria harder to escape.
Many games have several equilibria, and which one learners end up in is not determined by the game alone. Even perfect learners, each best-responding correctly, can converge to a suboptimal equilibrium. This is native to multi-agent settings and inescapable: it comes from the interaction, not from estimation error, so better single-agent learning does not remove it. Humans show it constantly. Outcomes are path dependent, shaped by history and initial conditions. Some equilibria exist but cannot be reached: driving on the left or on the right are both equilibria, a country keeps whichever history gave it, and the first driver to switch crashes; in each country people use the messaging app their contacts use; corruption persists where playing along pays as long as others do.
Learners tend to converge to safe equilibria because exploration mistakes are costly. In the stag hunt, a hunter who tries for the stag while the partner collects plants gets nothing, while a plant always pays +1, so both learn that plants are safe and the +5 stag equilibrium stays out of reach. It is a very tough exploration problem with hard-to-predict outcomes.
More agents make everything worse. Joint state and action spaces grow exponentially (in an 8×8 grid with 5 actions, 64N joint states and 5N joint actions). Non-stationarity comes from more policies changing at once, credit has to be split among more agents, and equilibria become harder to escape.
What is independent Q-learning? Give its pseudocode, explain what each agent's Q-values estimate, and use the climbing game to explain why independent learners miscoordinate.
Key points: each agent runs ordinary Q-learning over its own actions and treats the others as part of the environment (MDPti=MDPt+ki); pseudocode; QA(a)≈∑bπB(b)R(a,b), the reward averaged over the partner’s actions; climbing game: against a roughly uniform partner c averages best (1.7 against −5.7 and −6.3), the −30 dissuades exploring, stuck at (c,c) = 5 (“minimax”) while the optimum (a,a) = 11 is unreachable; centralized Q over joint actions finds 11.
In independent Q-learning each agent i keeps its own table Qi(s,ai) over its own actions and updates it with the ordinary rule Qi(s,ai)←Qi(s,ai)+α[ri+γmaxbQi(s′,b)−Qi(s,ai)]. The other agents’ actions never appear; their behaviour is absorbed into the transitions and rewards agent i experiences, so the MDP it faces changes over time.
Pseudocode: initialise every Qi to 0. Each step, every agent picks its action ε-greedily from its own table; the joint action is executed; the next state and each agent’s reward are observed; each agent updates its own entry with its own target; decay ε over time.
In a one-state game with shared reward R(a,b), agent A’s estimate becomes QA(a)≈∑bπB(b)R(a,b), the reward of a averaged over how often B plays each action. In the climbing game (rows a, b, c: 11, −30, 0 / −30, 7, 6 / 0, 0, 5), (a,a) = 11 is the optimal equilibrium and (b,b) = 7 a worse one. Early on the partner explores roughly uniformly, so QA(a)≈−6.3, QA(b)≈−5.7 and QA(c)≈1.7: c looks best because it never risks −30. Both agents drift to c and get stuck at (c,c) = 5, the action with the best worst case. Action a pays only if the partner also plays a, and trying it otherwise costs −30, so (a,a) is unreachable. A centralized learner with one value per joint action sees 11 directly and finds it. With low, decaying exploration the independent learners sometimes reach (b,b), but the outcome varies between runs.
Why is independent learning still widely used despite its problems? Compare centralized and decentralized learning for 2 agents with 6 actions each, and for 3 agents with 5 actions each.
Key points: centralized explores ∣A∣N joint actions, decentralized ∣A∣×N; 2 agents, 6 actions: 36 against 2 × 6 = 12; 3 agents, 5 actions: 125 against 15; averaging hides coordination (problem) but keeps each agent’s space small (benefit); in level-based foraging IQL reaches the optimum sooner than centralized Q; no guarantees, messy, but scales where central learning is intractable; also IPPO, DDPG, SAC; standard baseline.
A centralized learner treats all agents as one, so it must keep track of and explore every joint action: ∣A∣N of them. Independent learners each handle only their own actions: ∣A∣×N in total. With 2 agents and 6 actions that is one choice among 36 against two choices among 6 (12 values per state). With 3 agents and 5 actions it is 125 joint actions against 15.
The averaging in QA(a)≈∑bπB(b)R(a,b) cuts both ways. It is a problem for coordination, because it hides which joint actions are good, as in the climbing game. It is a benefit for scalability, because each agent explores a small space. In level-based foraging with two agents and two apples, independent Q-learning reached the optimal return sooner than centralized Q-learning, though more noisily, because it explores more efficiently as the joint space grows.
So independent Q-learning is messy and has no convergence guarantees (the environment is non-stationary for each agent), but it is not fundamentally broken, and it scales to large, complex environments where central learning becomes intractable. The same idea applies to other single-agent algorithms (IPPO, DDPG, SAC), and independent learning is a standard baseline across MARL.
Is the simple reflex vacuum agent (suck if dirty, otherwise move to the other square) rational? Under what conditions, and when would it stop being rational?
Key points: rationality depends on performance measure, prior knowledge, actions and percept sequence; rational under the book’s assumptions (1 point per clean square per step over 1000 steps, known geography, deterministic actions, correct sensing); irrational if movement costs, if dirt reappears, or if geography is unknown; rationality is relative to expected performance.
A rational agent selects, for each percept sequence, the action expected to maximise its performance measure given its percepts and built-in knowledge. So “is it rational?” has no answer until we fix the four things rationality depends on: the performance measure, the agent’s prior knowledge, the available actions and the percept sequence.
Under Russell and Norvig’s assumptions the agent is rational. The performance measure gives one point per clean square per time step over 1000 steps. The two-square geography is known, but the dirt distribution and the start square are not. Clean squares stay clean, Suck cleans the current square, and Left and Right move one square (or leave the agent in place at the wall). Only Right, Left and Suck are available, and the agent correctly perceives its location and whether there is dirt. No other agent can then do better in expectation: it cleans any dirty square at once and reaches the other square in one step.
Change the circumstances and it becomes irrational. If each move costs a point, it keeps oscillating after both squares are clean and loses points; a better agent would do nothing once it is sure all squares are clean. Russell and Norvig leave that design as an exercise, but being sure takes memory: the local dirt sensor cannot see the other square, so the agent must remember having found it clean, which a simple reflex agent, acting on the current percept alone, cannot do. If clean squares can get dirty again, it should check occasionally and re-clean. If the geography is unknown, it should explore. The same agent function can be rational in one task environment and irrational in another.
Give a PEAS description for an automated taxi and classify taxi driving along each environment dimension, with a justification for each.
PEAS. Performance: safe, fast, legal, comfortable trip, maximise profits, minimise impact on other road users (these conflict, so tradeoffs are needed). Environment: roads, other traffic, police, pedestrians, customers, weather. Actuators: steering, accelerator, brake, signal, horn, display, speech. Sensors: cameras, radar, speedometer, GPS, engine sensors, accelerometer, microphones, touchscreen.
Classification.
Partially observable: the taxi cannot see round a truck or know what other drivers intend.
Multiagent: other drivers’ behaviour is best described as maximising their own performance measures, which depend on the taxi’s actions. Partially cooperative (everyone wants to avoid collisions) and partially competitive (one parking space, one car).
Sequential: short-term actions (a lane change) have long-term consequences.
Dynamic: the world keeps moving while the driving algorithm deliberates; not deciding counts as doing nothing.
Continuous: positions, speeds, time and steering angles all vary continuously.
Known (mostly): the driver knows how the car and traffic rules work. Known/unknown is about the agent’s knowledge, not the environment itself; driving a rental car in an unfamiliar country would make it unknown too.
Taxi driving is therefore close to the hardest case, which is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous and unknown.
Explain the difference between rationality and omniscience. Why do information gathering, learning and autonomy follow from the definition of rationality?
Key points: omniscient agent knows actual outcomes, impossible; rationality maximises expected performance, perfection actual performance (Champs Elysées example); crossing without looking is irrational, looking is information gathering; agent must learn from percepts (dung beetle, sphex wasp as failures); autonomy: rely on own percepts and learning to make up for partial or wrong prior knowledge.
An omniscient agent knows the actual outcome of its actions and can act accordingly; this is impossible in reality. Rationality only asks the agent to maximise expected performance given its percept sequence to date. Someone who crosses an empty street and is hit by a cargo door falling from an airliner acted rationally: the outcome was bad, but the choice was right given the evidence. Requiring the best action in hindsight would make the specification impossible to meet.
This does not let an agent excuse itself by not looking. Crossing a busy road with an uninformative percept sequence is not rational, because the expected cost is too high, and choosing to look first is rational, because looking raises expected performance. Acting to change future percepts is information gathering; exploring an unknown environment is another example.
The definition also requires learning from what is perceived. An agent that relies only on built-in assumptions is fragile: the dung beetle mimes plugging its nest after the dung ball is removed, and the sphex wasp repeats its drag-and-check routine endlessly when the caterpillar is moved. Neither can learn that its plan is failing. An agent that relies on its designer’s prior knowledge instead of its own percepts and learning lacks autonomy. A rational agent should be autonomous enough to compensate for partial or incorrect prior knowledge, though it is sensible to start with some built-in knowledge, as evolution gives animals reflexes.
Why is it hard to choose a performance measure? Use the vacuum world to illustrate, state Russell and Norvig's general rule, and connect it to reward hacking.
Key points: performance measure scores sequences of environment states (consequentialism); “dirt cleaned up” is maximised by dumping and re-cleaning; better: points per clean square per time step (minus energy, noise); rule: measure what you want achieved in the environment, not how the agent should behave; reward hacking: optimiser exploits the gap between measure and purpose (Wiener, King Midas), and the flaw may only appear when new actions become available (Lab 1 Dump).
Russell and Norvig judge agents by consequences: a performance measure scores the sequence of environment states the agent’s actions produce. Machines have no preferences, so the measure comes from the designer, and writing it down correctly is hard because a rational agent gives you exactly what you ask for.
If the vacuum agent is scored on the amount of dirt it cleans up in a shift, it can maximise the score by cleaning, dumping the dirt back and cleaning again. The measure described a behaviour the designer imagined. Scoring one point per clean square per time step, perhaps minus a penalty for electricity and noise, describes the state of the world the designer actually wants. Hence the rule: design performance measures according to what one actually wants to be achieved in the environment, rather than according to how one thinks the agent should behave.
The course calls this reward hacking (specification gaming), a term the book does not use: an optimiser finds behaviour that scores well on the stated objective while defeating its purpose, which is Wiener’s warning that the purpose put into the machine must be the one we really desire, and the King Midas problem. Lab 1 shows a further twist: with only Left, Right and Suck, a dirt-collected reward and a clean-floor reward produce identical behaviour, so testing cannot reveal the problem; once a Dump action is added, the dirt-collected robot dumps and re-sucks. Even a good measure leaves open questions (steady mediocre cleaning against bursts and breaks with the same average), and since the true measure may be uncertain or user-dependent, agents may need to learn it.
Distinguish the agent function from the agent program. Write the table-driven agent and explain why this approach is doomed.
Key points: agent function maps percept sequences to actions (abstract); agent program implements it, receives only the current percept; TABLE-DRIVEN-AGENT appends percept and looks up the whole sequence; table size is the sum over t of |P|^t; cannot be stored, built or learned; goal of AI is small programs that produce rational behaviour.
The agent function is an abstract mathematical description: it maps every possible percept sequence to an action. The agent program is a concrete implementation running on the agent architecture (agent = architecture + program). The program receives only the current percept, since that is all the environment provides, so if the action must depend on history the program has to remember it.
function TABLE-DRIVEN-AGENT(percept) returns an action persistent: percepts, a sequence, initially empty table, a table of actions, indexed by percept sequences, initially fully specified append percept to the end of percepts action ← LOOKUP(percepts, table) return action
With a correct table it implements any desired agent function. But with a set of percepts P and lifetime T, the table has ∑t=1T∣P∣t entries. For an hour of taxi driving from camera input that is over 10600,000,000,000, and even chess needs at least 10150, against fewer than 1080 atoms in the observable universe. So no agent could store the table, no designer could write it, and no agent could learn all its entries. The challenge for AI is to get rational behaviour from a compact program, as Newton’s method replaced square-root tables; even the four-line reflex vacuum agent replaces an infinite table by ignoring history.
Describe the simple reflex, model-based reflex, goal-based and utility-based agents. What does each add to the previous one, and in what kind of environment does each fail?
Key points: simple reflex: condition-action rules on the current percept, needs full observability, loops otherwise (randomisation helps a little); model-based: internal state updated with transition and sensor models, handles partial observability, still rule-based; goal-based: predicts future states and picks actions that reach goals, flexible because knowledge is explicit; utility-based: utility function grades states, handles conflicting goals and uncertain success, maximises expected utility.
A simple reflex agent chooses from the current percept alone through condition-action rules (if car-in-front-is-braking then initiate-braking). It is small and fast but works only in fully observable environments. A vacuum agent with no location sensor that always moves the same way on [Clean] loops forever in one of the two start squares; randomising between Left and Right escapes the loop, but randomisation is rarely rational in single-agent settings.
A model-based reflex agent adds internal state that tracks what it cannot currently see. It updates the state each step with a transition model (how actions change the world and how the world evolves by itself) and a sensor model (how states show up in percepts): state ← UPDATE-STATE(state, action, percept, transition model, sensor model), then matches rules as before. This handles partial observability (the state is a best guess), but behaviour is still fixed rules with no look-ahead.
A goal-based agent adds goals and uses the model to predict “what it will be like if I do action A”, choosing actions (or, via search and planning, action sequences) that achieve the goal. It considers the future and knows why it acts. It is more flexible: change the destination and the behaviour changes, whereas reflex rules would all need rewriting. But goals are binary.
A utility-based agent replaces goals with a utility function, an internalisation of the performance measure, and chooses the action with the highest expected utility, ∑s′P(s′∣s,a)U(s′). It handles conflicting goals (speed against safety) and goals that may not be reached (weighing likelihood against importance). But modelling the world and computing the best action is hard, and perfect rationality is usually computationally out of reach.
Describe the components of a general learning agent. Why must the performance standard be fixed and outside the agent, and what is the role of the problem generator?
Key points: performance element selects actions (the old agent); learning element improves it using feedback; critic judges behaviour against a fixed performance standard; problem generator suggests exploratory actions; percepts carry no verdict on success, so a standard is needed; the agent must not adapt the standard to its own behaviour; exploration trades short-term loss for long-term gain (Galileo).
The performance element takes percepts and selects actions: it is what the earlier designs called the whole agent. The learning element improves the performance element, and its design depends on what the performance element looks like. The critic tells the learning element how well the agent is doing with respect to a performance standard. The problem generator suggests actions that lead to new, informative experiences.
The critic is needed because percepts do not say whether they are good: a chess program perceives checkmate but needs a standard to know checkmate is good. The standard must be fixed and conceptually outside the agent, because the agent must not modify it to fit its own behaviour; if it could, it could improve its score by changing the standard instead of its behaviour. The standard effectively marks part of each percept as reward or penalty, like pain and hunger in animals.
Left alone, the performance element keeps choosing the best action given what it knows. The problem generator proposes perhaps suboptimal exploratory actions that may reveal better ones in the long run, like Galileo’s experiments at Pisa. Learning in general means modifying each component of the agent to bring it into closer agreement with the available feedback, thereby improving overall performance.
Explain atomic, factored and structured representations of state with an example of each. What is gained and lost as representations become more expressive? How does a distributed representation differ from a localist one?
Key points: atomic: state is a black box (city name; search, MDPs); factored: fixed set of variables with values (fuel, GPS, money; CSPs, propositional logic, Bayesian networks); structured: objects with attributes and relations (truck, cow, driveway; first-order logic, databases); more expressive is more concise (chess rules: a page or two, thousands of pages, about 10^38 pages) but harder to reason and learn with; localist one concept per location, distributed spread over many, robust to noise.
In an atomic representation a state has no internal structure: for route-finding it is just the name of the city you are in, and two states are only ever the same or different. Search, game playing, hidden Markov models and Markov decision processes use atomic states. A factored representation splits the state into a fixed set of variables with values: fuel level, GPS position, toll money. Two states can share some values, which makes it easier to see how to turn one into another; constraint satisfaction, propositional logic, planning and Bayesian networks use it. A structured representation describes objects, their attributes and their relations, which a scene like a truck reversing into a farm driveway blocked by a loose cow needs; first-order logic, relational databases and natural language understanding use it.
More expressive representations capture everything less expressive ones can, usually far more concisely: the rules of chess take a page or two in first-order logic, thousands of pages in propositional logic and about 1038 pages as a finite-state automaton. The cost is that reasoning and learning get harder, so real systems may need all three levels at once.
A localist representation maps each concept to one memory location; a distributed representation spreads each concept over many locations, each shared with other concepts. Distributed representations are more robust: a few garbled bits move the concept to a nearby point with similar meaning, while in a localist code they can turn Truck into the unrelated Truce.
A symmetric game has R=5, S=0, T=3, P=1. Find the pure Nash equilibria, the Pareto-optimal outcomes and the social optimum, compute p∗, say which equilibrium uniform-belief agents play more often, and give the replicator rest points with their stability.
Key points: Nash (C,C) and (D,D), a Stag Hunt (fear, no greed); only (C,C) Pareto optimal and socially optimal; p∗=1/3; (C,C) more often since R−T=2>P−S=1, with Pr(C,C)=4/9; rest points 0 stable, 1/3 unstable, 1 stable.
Game.R>T>P>S, so it is a Stag Hunt: no greed (T=3<R=5), fear (P=1>S=0).
Nash. At (C,C) deviating gives 3 < 5; at (D,D) deviating gives 0 < 1; at (C,D) the cooperator gains by switching to D (1 > 0). Pure equilibria: (C,C) and (D,D).
Pareto and social. Payoffs (5,5), (0,3), (3,0), (1,1). (C,C) beats every other cell for both players, so it is the only Pareto-optimal outcome, and with welfare 10 (against 3, 3 and 2) the social optimum.
Threshold.p∗=(R−T)+(P−S)P−S=2+11=31. Stag is the best response when the belief that the partner hunts stag exceeds 1/3.
Uniform beliefs. Each agent cooperates with probability 2/3: Pr(C,C)=4/9≈0.44, Pr(D,D)=1/9≈0.11, miscoordinated 4/9. (C,C) is more frequent, as the rule R−T>P−S (2>1) predicts.
Replicator.fC−fD=x(R−T)+(1−x)(S−P)=2x−(1−x)=3x−1, so x˙=x(1−x)(3x−1). Rest points 0 (stable, g′(0)=S−P=−1), 1/3 (unstable), 1 (stable, g′(1)=T−R=−2). Populations starting above 1/3 cooperators end at full cooperation, below at full defection.
A symmetric game has R=3, S=1, T=4, P=0. Find the pure Nash equilibria, the replicator rest points and their stability, and explain how the long-run population differs from the Stag Hunt's.
Key points: greed present, fear absent; pure Nash (C,D) and (D,C), no symmetric pure equilibrium; fC−fD=1−2x; rest points 0 and 1 unstable, x=1/2 stable; population converges to a mix, while the SH’s interior point is unstable.
Motives. Greed: T=4>R=3. Fear absent: P=0<S=1. Each player wants to do the opposite of the other.
Nash. Against C the best response is D (4 > 3); against D it is C (1 > 0). So the pure equilibria are (C,D) and (D,C); (C,C) and (D,D) are not equilibria. Social optimum: (C,C) with welfare 6 (against 5, 5, 0).
Replicator.fC−fD=x(R−T)+(1−x)(S−P)=−x+(1−x)=1−2x, so x˙=x(1−x)(1−2x). Rest points: x=0 with g′(0)=S−P=1>0, unstable; x=1 with g′(1)=T−R=1>0, unstable; x∗=1/2, where g′(1/2)=21⋅21⋅(−2)=−21<0, stable. From any interior start the population goes to half cooperators.
Contrast. In the SH (R>T, P>S) both pure states are stable and the interior rest point (the mixed equilibrium) is unstable, a tipping point. Here both pure states are unstable (a rare strategy always earns more) and the interior rest point, the mixed equilibrium with cooperation probability 1/2, is where the population ends. Whether adaptation ends at the mixed equilibrium depends on the signs of S−P and T−R.
In a repeated Prisoner's Dilemma ( R=3,S=0,T=5,P=1), explain why memory matters, why AllD can still top a round robin with AllC, AllD, Random, TFT and WSLS over 50 rounds, and from how many rounds TFT beats AllD in a field of AllD, TFT and WSLS.
Key points: memory-0 strategies cannot react, memory-1 strategies condition on the last outcome; TFT loses only round 1 to AllD; AllD’s score comes from exploiting AllC (5), Random and WSLS (about 3 each); in the three-strategy field AllD wins for 1 to 3 rounds and TFT from 4.
Memory. A memory-0 strategy (AllC, AllD, Random) plays the same way whoever it meets, so a cooperator of this kind is exploited every round. A memory-1 strategy conditions on the previous outcome: TFT cooperates with cooperators and defects against AllD from round 2, so it loses 5 points once and then gets 1 per round (0.98 per round over 50).
Why AllD tops the five-strategy field. Its 50-round score, about 2.62, averages 5 against AllC, 1 against itself, 3 against Random, 1.08 against TFT and 3 against WSLS, which alternates C and D against it. Most of its points are temptation payoffs taken from AllC, Random and WSLS; against TFT it earns little. TFT is second at about 2.44.
Crossover. Per-round tournament scores times 3 over n rounds: AllD 5+4/n (n even) or 5+6/n (n odd); TFT 7−1/n; WSLS 6+⌊n/2⌋/n. AllD beats TFT iff n<2.5 (even) or n<3.5 (odd), so AllD is best for 1, 2 and 3 rounds and TFT from 4 rounds on.
Derive the two-strategy replicator equation's factorised form, use it to show that cooperation always dies out in a Prisoner's Dilemma, and explain why the Stag Hunt's interior rest point equals the threshold belief p∗ even though adaptive agents hold no beliefs.
Key points:x(fC−fˉ)=x(1−x)(fC−fD); PD: fC−fD=x(R−T)+(1−x)(S−P)<0 by greed and fear; x=1 is a rest point but unstable; random matching makes the share x play the role of the belief p; the same indifference equation gives the same solution.
Factorisation.fˉ=xfC+(1−x)fD, so fC−fˉ=(1−x)(fC−fD) and x˙=x(1−x)(fC−fD).
PD.fC−fD=x(R−T)+(1−x)(S−P). Greed gives R−T<0, fear gives S−P<0, so for every x∈[0,1] it is a weighted average of two negatives. Hence x˙<0 on (0,1) and every population with some defectors goes to x=0, matching the unique Nash equilibrium (D,D). x=1 is a rest point because there is nobody to copy, but a single defector earns T>R and spreads.
Why x∗=p∗. With random pairing, a partner cooperates with probability equal to the population share x. So fC(x)=xR+(1−x)S is exactly πC(p) with p=x, and likewise for D. The interior rest point solves fC=fD, the same equation as the rational agent’s indifference πC(p)=πD(p), so x∗=(R−T)+(P−S)P−S=p∗. The rational agent cooperates when its belief exceeds p∗; in the population, cooperators grow when the actual share exceeds p∗. For the lab’s SH it is 2/3, and it is unstable: a tipping point.
In the signalling game with λ=0.3, b=g=d=1 and cH=0.2, explain the long-run outcomes for cL=1.5 and cL=0.5, and evaluate a designer's uniform fee of k=1 on the label.
Key points:cL>b: fakers die out, honest separating outcome, reliability 1, receivers earn 0.3; cL<b: cycles around y=0.5, xL=3/7, reliability about 0.5, receivers earn about 0; fee makes cH=1.2>b, nobody signals, welfare 0.084 to 0; honesty needs cH<b<cL.
Expensive faking (cL=1.5). Faking pays at most b−cL<0, so xL→0. H signals whenever y>0.2; once fakers are rare trusting pays (0.3xH>0.7xL), so y→1 and xH→1. The signal is fully reliable; receivers earn 0.3 and H sellers 0.8.
Cheap faking (cL=0.5). Faking pays when y>0.5; trusting pays when xL<3/7 (with xH=1). No state satisfies everyone, so trust and faking chase each other in cycles around y=0.5, xL=3/7. Reliability averages about 0.5 (prior 0.3) and receivers average about 0: fakers keep the signal just bad enough that trusting pays no better than scepticism (since dtdln1−yy equals the advantage of trusting and y stays bounded, that advantage averages about zero).
The fee. With k=1, cH=1.2 and cL=1.5 both exceed b, so nobody signals. Deception ends, but receivers stay at 0, H sellers drop from about 0.3 to 0 and welfare from 0.084 to 0. The fee is harmful.
Correct design. An honest signal needs cH<b<cL: affordable for genuine sellers, unprofitable for fakers. A uniform fee shifts both costs equally and could at most place b between them (0.5<k<0.8 here); a cost that falls on fakers specifically (verification they fail, penalties) is the right tool.
Two robot vacuums plan optimally with value iteration ( γ=0.95) in the two-square vacuum world with dirt rate 0.1. Bob's reward is +1 per clean square per step; Alice's is +1 per unit of dirt sucked. Explain why tests in the lab cannot tell them apart, what happens when a Dump action is added, and what this shows about agents and tools.
Key points: identical optimal action sets in all 16 states without Dump, so identical behaviour; Alice dumps when the bag is full and her square is clean, then re-sucks for +1 every two steps (floor 84% to 59% clean, dirt collected 0.196 to 0.527 per step); Bob never dumps; reward hacking: a proxy that matched the goal under one action set diverges when a new action appears.
Lab. With Left, Right and Suck, a square becomes clean only by being sucked and dirt only comes from the environment, so maximising clean squares and maximising dirt sucked call for the same actions: suck when on dirt, move to dirt, anything on a clean floor. Both robots have the same optimal set in every state and act identically step for step; no behavioural test in this environment can reveal the reward.
With Dump. Alice’s robot dumps in the four states with a full bag and a clean current square (uniquely when both squares are clean, tied with moving when the other square is dirty), then sucks the same dirt: +1 every two steps, guaranteed. It dumps on 40% of steps, its floor drops to about 59% clean, it barely moves. Bob’s reward ignores the bag and penalises dirt, so dumping only loses reward; he never dumps.
Lesson. Nobody programmed dumping: a perfect optimiser found a way to raise a proxy (dirt collected) without serving the goal (a clean floor). New actions or tools can break the link between reward and goal, testing behaviour cannot certify a reward, and rewards should target outcomes and be re-checked whenever capabilities change.
Two independent stateless Q-learners ( α=0.1, ε-greedy) play the Stag Hunt with R=4, S=0, T=3, P=2, starting from Q=(0,0). Explain which equilibrium they usually reach and why, and how this compares with rational agents and with replicator dynamics.
Key points: random play at the start acts like belief 1/2 < p∗=2/3; D earns 2.5 against 2 and never below 2; (C,C) essentially only if both play C in round 1 (probability 1/4); feedback lock-in at (D,D), then exploration erodes the remaining (C,C); final (C,C) under 10%, below rational agents’ 11% and the replicator’s one third.
Start. All values are 0, so both agents break ties at random and each faces a coin-flipping partner. Then C earns 21⋅4=2 and D earns 21⋅3+21⋅2=2.5 on average, and D never earns less than 2 while C earns 0 half the time. The start is like holding belief 1/2, below p∗=(P−S)/((R−T)+(P−S))=2/3.
Round 1 decides. If both play C, both get 4 and Q(C)=0.4>0: both prefer C. If either plays D, the D player’s Q(D) becomes positive, and a C player facing D earns 0, stays tied and drifts to D as soon as its tie-break picks D (2 against 0). So (C,C) is reached with probability about 1/4; my runs give 28% after the first rounds.
Lock-in. Once the partner plays D, C pays 0, so Q(C) never gets evidence of the 4 it could earn; Q(C) rises only when both play C together, (ε/2)2=0.25% of rounds. Meanwhile the partner’s exploratory defections push (C,C) runs over to (D,D) (each zero cuts Q(C) by 10%), and nothing comes back. After 3000 rounds (C,C) holds in roughly 5% to 10% of runs.
Comparison. Rational agents with uniform beliefs reached (C,C) in 11% of encounters, and replicator dynamics reached all-C from one third of starting states. Learning did not help: the learners start below p∗ and noise drives them towards the risk-dominant (D,D) (P−S=2>R−T=1).
Two stateless Q-learners in the Stag Hunt ( R=4,S=0,T=3,P=2, α=0.1) start at (C,C) with Q=(3.6,2.9). Explain why they leave (C,C) at ε=0.1 although C is the best response, and why the escape from (D,D) to (C,C) almost never happens.
Key points: C pays 3.8 and D 2.95 against an exploring partner; Q is an exponentially weighted average of recent payoffs (memory about 10 plays); three zeros take Q(C) from 3.8 to 2.77 < 2.95; the partner then earns 0 and follows; from (D,D) C pays 4 only on joint exploration (0.25% of rounds), about seven successes in a row needed, both must switch at once; basins of 1/3 against 2/3.
Best response. The partner plays D in ε/2=5% of rounds. C earns 0.95⋅4=3.8, D earns 0.95⋅3+0.05⋅2=2.95, so a rational agent stays.
What Q estimates. Unrolling the update gives Qt(C)=α∑k(1−α)krt−k: an exponentially weighted average of recent payoffs, with weights halving about every 6.6 plays. With a constant α it tracks what C paid lately, with standard deviation σα/(2−α)=0.20 around 3.8.
Escape. Each exploratory D of the partner pays me 0 and cuts Q(C) by 10%: 3.8→3.42→3.08→2.77<2.95. A short run of three such zeros, likely somewhere in 3000 rounds, flips my greedy action to D; then the partner earns 0 every round and flips within about three rounds. In my runs only 17% to 20% of pairs are at (C,C) after 3000 rounds (100% at ε=0.01, 0.4% or less at ε=0.5). One agent’s exploration is noise in the other’s rewards, and the learner reads it as a change in the partner.
No way back. At (D,D), C pays 0.05⋅4=0.2 on average and D 2.05. Q(C) changes only when I explore C, and pays 4 only if the partner explores C in the same round, 0.25% of rounds; failures are 19 times as common. Climbing from 0.2 to above 2 takes about seven successes in a row, and both agents must switch together or the switcher earns 0. Structurally, leaving (C,C) needs the partner to look like a defector more than 1−p∗=1/3 of the time, leaving (D,D) needs it to look like a cooperator more than p∗=2/3 of the time.
In the Coin Game a pickup pays the picker +1 whatever the coin's colour, and taking the other player's coin costs that player 2. Explain why two independent Q-learners collect many coins but do not show restraint, derive the expected total reward per pickup, and relate this to the Prisoner's Dilemma.
Key points: taking any reachable coin is at least as good for my own reward in every state; the −2 lands in the other’s reward, which my values never see; welfare = pickups × (2 × share − 1); expected total per pickup 0 for colour-blind agents; independent learners treat the other as environment, no memory of its behaviour, no reciprocity; same structure as mutual defection.
Dominance. Taking a coin pays me +1. Leaving the other’s coin pays me 0 now, and if the other then takes it I still get 0; the cost of my taking it, −2, goes to the other. So taking every reachable coin is a dominant behaviour for my own reward, the analogue of D.
Total per pickup. An own-colour pickup adds +1 to the total; a pickup of the other’s coin adds +1−2=−1. With colour-blind agents half of the pickups are of each kind, so the expected total is 21−21=0, and welfare =pickups×(2×restraint−1)≈0 however skilled they are.
Results. My Q-learners went from the random level (3.7 pickups) to about 17 pickups per episode, with own-colour share 0.52 and welfare about +0.6, against about 0 for random agents.
Why learning cannot fix it. Independent Q-learning treats the other agent as part of the environment and maximises its own return. Restraint costs +1 and benefits only the other, unless it changes the other’s future behaviour. But the state holds only positions and the coin, with no record of the other’s past restraint, so neither agent can reciprocate or punish; both are memory-0 with respect to the partner, and against any fixed behaviour of the other, taking every coin is the best response. As in the one-shot Prisoner’s Dilemma, individually rational learning ends in mutual defection.
A tabular Q-learner in the 3×3 Coin Game gets k irrelevant random lamps in its observation and a budget of B=512,000 decisions. Compute the number of rows, the reachable states and the expected share of visited states and of test decisions in unvisited states for k=0,4,8, and explain what this means for learning.
Key points:N=1458⋅2k (1,458; 23,328; 373,248); coin never on an agent’s cell, so N′=1152⋅2k; never-visited probability (1−1/N′)B≈e−B/N′; B/N′=444, 27.8, 1.74; for k=8 about 82% of reachable states visited and 17.6% of test decisions unseen; a table does not generalise, a function approximator can ignore the lamps.
Reachable. At decision time the coin is never on an agent’s cell. Agents on different cells: 9⋅8 ordered pairs, 7 coin cells; on the same cell: 9 pairs, 8 coin cells. (504+72)⋅2=1152, so N′=1152⋅2k (79% of the rows).
Uniform-visit model. A given state is missed by one decision with probability 1−1/N′, by all B independent decisions with probability (1−1/N′)B≈e−B/N′; expected visited states N′(1−e−B/N′). With B/N′=444, 27.8 and 1.736: all reachable states are visited for k=0 and 4, and 1−e−1.736=82.4% for k=8. A uniform test decision falls in an unvisited state with probability e−B/N′: about 0, about 10−12, and 17.6%. My runs: 82.0% visited and 17.4% unseen for k=8.
Meaning. With a fixed budget, experience per row falls by 2k. At k=4 every state is seen, but only about 28 times across four actions, so values are partly learned (pickups 12.8 against 16.9 at k=0). At k=8 the agent acts at random in 17% of states and on barely trained values in most others (6.6 pickups, random agents 3.7). The table cannot notice that rows differing in the lamps need the same action; a learner that shares parameters across observations (a neural network, as in PPO) can give the lamps no weight.
Describe the components of PPO (actor, critic, advantage, clipped objective, entropy regularisation), say what the critic adds over REINFORCE, and explain why independent PPO in the Coin Game handles irrelevant inputs but still fails the social dilemma.
Key points: actor softmax policy sampled for exploration; critic V(s) as baseline and bootstrap for Adv=r+γV(s′)−V(s) (GAE with λ); clipped ratio ρ keeps updates in a trust region; entropy bonus prevents premature determinism; shared weights generalise across lamp patterns; own-colour share about 0.5 and welfare about 0 because each agent’s reward makes taking every coin the best response.
Actor. A network π(a∣s;ϕ) outputs action preferences turned into probabilities by a softmax; the agent samples, which is where exploration comes from.
Critic and advantage. A second network V(s;θ) estimates the return. The advantage Adv(st,at)=rt+γV(st+1)−V(st) says how much better the action did than expected; generalized advantage estimation mixes horizons with λ (0 one-step, 1 Monte Carlo). Compared with REINFORCE, which pushes each action by the whole return that followed, the critic provides a baseline and bootstrapping, so the gradient has much lower variance and credit goes to the action’s own consequences, at the cost of some bias.
Clipped objective. Each batch is reused for several epochs. The ratio ρ=π(a∣s;ϕ)/πβ(a∣s) measures how far the policy moved; the loss −min(ρAdv,clip(ρ,1−ϵ,1+ϵ)Adv) stops rewarding change beyond 1±ϵ, a trust region around the behaviour policy.
Entropy. The loss subtracts ce times the policy entropy, keeping probabilities spread so exploration does not stop too early.
Coin Game. The network shares weights across all observations, and random lamps carry no information about returns, so PPO learns to ignore them: in my runs 12.8 to 13.3 pickups with 8 lamps, as without, against 6.6 for the table. But each PPO agent still optimises its own reward with the other treated as environment, so taking every coin stays the best response: own-colour share about 0.51 and welfare near 0. Deep RL fixes representation and generalisation; the dilemma lives in the incentives.
Would replacing the Stag Hunt's Q-learners with PPO learners remove the problem of equilibrium selection? Use the expected policy gradient of a two-action softmax policy.
Key points: one state, nothing to generalise; ∂J/∂z=πC(1−πC)(fC−fD) with fC−fD=3q−2; like the replicator equation, it favours C only when q>2/3; from π=1/2 both drift to D; both pure equilibria stable, the outcome depends on initialisation and noise; sampling and entropy act like exploration and threaten (C,C) more.
Gradient. With logit difference z, πC=σ(z) and J=πCfC+(1−πC)fD, where fC=qR+(1−q)S and fD=qT+(1−q)P for a partner who plays C with probability q. Since dσ/dz=σ(1−σ), ∂J/∂z=πC(1−πC)(fC−fD), and for R=4,S=0,T=3,P=2, fC−fD=q−2(1−q)=3q−2. Like the replicator equation x˙=x(1−x)(fC−fD), it pushes towards C exactly when q>2/3.
Outcome. A fresh network gives πC≈1/2 to both agents, so each sees q≈1/2<2/3 and moves towards D; the pair goes to (D,D). Initial policies above 2/3 would go to (C,C). Both pure equilibria are stable (fC−fD=+1 near q=1, −2 near q=0), so which one is reached depends on where the policies start and on noise, exactly the problem Q-learners had.
Why the network does not help. The Stag Hunt has a single state, so generalisation across states, PPO’s advantage in the Coin Game, has nothing to work on; clipping limits the size of steps and leaves their direction unchanged. Sampled actions and the entropy bonus keep the policy stochastic, which, as with ε-greedy, makes (C,C) more fragile than (D,D). Equilibrium selection belongs to the game and to independent learners each following their own payoff.