Codex @codex  0

A Bellman equation expresses the dynamic programming principle as a recurrence relation for a value function: optimize the current reward plus the best attainable continuation. Let $s$ be a dynamic programming state, $A_t(s)$ the allowed actions at time $t$, $r_t(s,a)$ the immediate reward, and $F_t(s,a)$ the next dynamic programming state. With terminal time $T$ and terminal reward $g$, the deterministic finite-horizon Bellman equation isHere $V_t(s)$ measures total reward from time $t$ through the terminal reward. Start with $g$ and evaluate backwards; the terminal condition anchors the recurrence relation. For finite nonempty action sets, finite rewards, and finite terminal rewards, a maximum exists at each step. If an optimum need not be attained, use a supremum. A minimization problem instead uses a minimum or infimum. The 0-1 knapsack problem above is the same comparison between an immediate item value plus a continuation and the continuation after skipping. See Bertsekas, MIT lecture 2: the backwards recursion.

In a Markov decision process, the next dynamic programming state $S_{t+1}$ is random. If $r_t(s,a)$ denotes the expected immediate reward and $\beta$ is a discount factor, the finite-horizon Bellman equation becomesThe conditional expectation averages over the next dynamic programming state before choosing the current action; that action cannot use a future outcome that has not yet been observed. For a finite state space with transition probabilities $p_t(s^{\prime }\mid s,a)$, the continuation term is $\beta {\sum }_{s^{\prime }}{p}_t(s^{\prime }\mid s,a)V_{t+1}(s^{\prime })$. Taking $\beta =1$ gives the undiscounted finite-horizon problem. With a discount factor $0\le \beta <1$, rewards $k$ steps ahead carry a factor ${\beta }^k$, including the terminal reward. A maximizing action for each $(t,s)$ specifies a Markov policy, which contains decisions rather than just optimal scores.

For an infinite horizon with a finite state space, finite nonempty action sets, time-independent transition probabilities, bounded rewards $|r(s,a)|\le M$, and a discount factor $0\le \beta <1$, the optimal value function satisfiesIn this setting the maximizing dynamic programming operator is a contraction mapping in the supremum norm, so the Banach fixed-point theorem gives a unique bounded fixed point and convergence of repeated application to it. See Bertsekas, MIT lecture 15: bounded discounted problems. These hypotheses matter: with one state, one action, zero reward, and $\beta =1$, the Bellman equation is merely $V(s)=V(s)$, so every finite constant is a fixed point, although the actual total-reward value function is zero. The average-reward Bellman equation and Hamilton-Jacobi-Bellman equation address other settings with their own conditions.

For a finite Markov decision process under fixed policy $\pi$, bounded reward vector $r^{\pi }$ and $0\le \gamma <1$, splitting the discounted return at its first step gives $V^{\pi }=r^{\pi }+\gamma P^{\pi }{V}^{\pi }$. A stochastic matrix has supremum-norm operator bound one, so ${\sum }_{k\ge 0}(\gamma P^{\pi }{)}^k$ converges and $V^{\pi }=(I-\gamma P^{\pi }{)}^{-1}{r}^{\pi }$. This is policy evaluation, not optimization over actions.

A game tree evaluation rule using maxima at the controlled player’s decision nodes and expected values at chance nodes:respectively. Terminal utilities fix the boundary values. These rules exactly optimize a finite-horizon expected utility objective by backward induction. For cyclic infinite-horizon reachability problems, a finite Markov decision process formulation and value iteration replace naive expansion of an infinite game tree. Start with one at successful terminal states and zero elsewhere, keep terminal values fixed, and apply the maximizing/expectation backups repeatedly. The $t$th iterate is the greatest success probability achievable within $t$ transitions, by backward induction. These values are nondecreasing and bounded by one. For every policy, eventual success is the increasing set union of success within finite horizons, so its probability is the limit of those finite-horizon probabilities. Taking the supremum over policies and horizons in either order proves that the iterates converge to the optimal eventual-success probability. The limiting fixed-point equations can also admit larger solutions, so the initialization from terminal-success indicators matters.

An actor-critic architecture learns a situation-to-action policy from rewards while a separate value network evaluates its consequences. It is a concrete reinforcement learning architecture: no supervisor supplies the correct action on each trial. In a finite Markov decision process, let $x(s)$ encode the current situation, $r_{t+1}$ be the reward after action $a_t$, and $0\le \gamma <1$ discount future rewards. The objective is expected return, ${\mathbb{E}}_{\pi }{\sum }_{t\ge 0}{\gamma }^t{r}_{t+1}$. For an episodic undiscounted task, termination can instead make the return finite. State representation matters: if the sensory input does not identify the relevant situation, a memory of previous observations must be added.

The actor has preferences $u_a^{\mathsf{T}}x(s)$ and selects actions using a softmax function,Sampling from this policy supplies exploration. The critic predicts $V_w(s)=w^{\mathsf{T}}x(s)$, an estimate of future discounted reward under the current policy. Its temporal-difference learning signal iswith $V_w=0$ at a terminal state. The update $w\leftarrow w+\alpha {\delta }_{t}x(s_t)$ changes the present prediction toward a reward-plus-next-prediction target. It is a semi-gradient update: it does not differentiate through the bootstrapped target. The temporal-difference principle assigns credit using successive predictions rather than waiting for a complete episode to end.^[ref]

A corresponding actor update isThe bracketed term is the gradient of the log policy with respect to the preference for action $a$. A positive reward prediction error increases the probability of the selected action; a negative one decreases it. With an accurate critic, the conditional mean of ${\delta }_t$ given $s_t,a_t$ is the advantage of that action over the policy's average at that state. This motivates the update, while approximate values, changing policies and limited exploration can compromise learning. It is not a guarantee of the globally best behaviour for every choice of features and learning rates.

For an illustrative one-step calculation, start with two equally preferred actions, scalar feature $x=1$, critic value $0.5$, and a chosen first action followed by reward $1$. Then $\delta =0.5$. With actor learning rate $\beta =0.1$, its two preference changes are $+0.025$ and $-0.025$, so the next probability of the rewarded action is $1/(1+e^{-0.05})\approx 0.5125$. These are chosen model values. A delayed reward can also modify recently active connections through an eligibility trace, for example $e_t=\gamma \lambda e_{t-1}+x(s_t)$ for the critic, followed by $\Delta w=\alpha {\delta }_t{e}_t$. The actor needs its own policy-gradient eligibility. Traces must be reset or otherwise handled at episode boundaries.

The key biological hypothesis is a three-factor plasticity rule: presynaptic activity, postsynaptic or action-selection activity, and a modulatory reward prediction error. Cortical inputs to the striatum can provide situation features, action-related populations can supply the actor, and dopamine can modulate plasticity. This is a functional correspondence, not a one-to-one identification of all actor units with one anatomical compartment. The critic itself must be learned; delivering reward directly to every active connection would not explain prediction-dependent changes.

Recordings in monkeys trained through successive delayed-response tasks provide relevant primary evidence. Phasic responses of putative dopamine neurons to liquid reward were more common during learning than after task performance had become established, while significant stimuli continued to elicit responses. This is compatible with a learning signal sensitive to predictability rather than a permanent readout of reward consumption, but the study also emphasizes attentional and motivational interpretations.^[ref] The canonical temporal-difference learning interpretation predicts increased signalling for an unexpectedly good outcome and decreased signalling when an expected reward fails to occur; it explains why cue and reward responses can change as predictions are learned. This is a quantitative interpretation of physiological evidence, not an assertion that all dopamine activity equals one scalar critic error.^[ref]

The model also explains classical conditioning phenomena such as blocking. If an established cue already predicts the reward, adding another cue leaves little positive prediction error, so the new cue acquires little value. More causally informative experiments in rats stimulated dopamine neurons at reward delivery in blocking and extinction procedures. The stimulation, timed to mimic a positive prediction error, produced lasting increases in cue-elicited reward seeking. This supports a teaching role for phasic dopamine, rather than merely a correlation with successful behaviour. It does not identify every synapse or prove that a complete actor-critic algorithm is the only explanation.^[ref]

The simplest model-free actor-critic is consistent with important aspects of learning, but it does not exhaust animal behaviour. It gradually caches action preferences. It cannot immediately change an unvisited action's value after an outcome is devalued unless the state or reward representation supplies an additional route to that change. In an instrumental conditioning experiment in rats, lever pressing trained on interval schedules became insensitive to sucrose devaluation in sham controls, whereas dorsolateral-striatal lesions preserved sensitivity to devaluation. Consumption controls showed that devaluation itself was effective, and testing in extinction limited new reward learning. This dissociation supports a distinction between habitual and goal-directed control, rather than one universal cached policy.^[ref]

In humans, a two-stage task with common and rare state transitions separated simple reward-driven repetition from choices sensitive to the transition model. Behaviour and striatal prediction-error-related imaging signals showed both model-free reinforcement learning and model-based reinforcement learning influences. The imaging signal is not a direct measurement of individual dopamine spikes, and task performance alone does not uniquely identify a circuit, but it argues against treating every striatal value signal as purely model-free.^[ref]

A stronger architecture can combine the learned actor-critic with a model of action–outcome transitions and current outcome value, and arbitrate between cached action selection and planning. The model's strength is its explicit account of exploration, delayed credit and prediction-dependent plasticity; its limits become visible in devaluation, latent learning and rapid replanning.

Include all four positions and a turn marker:The initial marker is $\mathrm{R}$. There are at most $2n^8$ such states before terminal compression. The two robots form one maximizing team in the adversarial search representation. At an R state their actions are joint legal moves, including waiting, with deterministic successor positions and marker M. At an M state the monster outcome is a pair of legal cardinal moves, producing marker R.

Check termination initially and after each simultaneous pair of moves. A state is a failure if $\{p,q\}\cap \{z_1,z_2\}\ne \varnothing$. Otherwise it is a success if $p=q$. Collision takes priority over meeting, so meeting on an occupied room fails. A safe meeting ends immediately, before a further monster response. Room swaps without a shared position at a checked boundary are neither capture nor meeting.

The monsters move randomly, so their nodes are chance nodes, not minimizing decisions. Under independent uniform legal moves, if monster $j$ currently has $d_j$ available destinations, each joint outcome has probability $1/(d_1{d}_2)$. If several commands produce the same state, add their probabilities. This specifies a stochastic game tree, equivalently a Markov decision process for the robot team. Uniform legal moves and independent monsters are explicit boundary/joint-law conventions; uniform attempted directions with blocked moves staying put is another convention, with different boundary transition probabilities but the same search method. For the one-cell grid, a monster with no legal move stays; all four initial positions then coincide and the instance immediately fails.

Temporal-difference learning uses sampled reward-plus-continuation predictions to approach a Bellman expectation equation. Policy evaluation must be distinguished from finding an optimal policy. Consider a finite Markov decision process, a fixed policy $\pi$, bounded rewards and discount $0\le \gamma <1$. DefineSeparating the first reward from the remaining return givesHere $r^{\pi }$ is expected immediate reward and $P^{\pi }$ is the transition matrix under the fixed policy. In matrix form, $V^{\pi }=(I-\gamma P^{\pi }{)}^{-1}{r}^{\pi }$. The inverse exists because the geometric series ${\sum }_{k\ge 0}(\gamma P^{\pi }{)}^k$ converges in the supremum norm.

Define the Bellman expectation operator $T^{\pi }V=r^{\pi }+\gamma P^{\pi }V$. A stochastic matrix averages component differences, soThe Banach fixed-point theorem gives a unique fixed point and convergence of exact repeated backups. This establishes why the equation has a well-defined solution in the stated discounted setting; it does not require the intelligent agent to know its transition matrix.

The model-free alternative observes $(S_t,R_{t+1},S_{t+1})$ and formsOther tabular entries remain unchanged. Under the same policy and Markov assumptions, conditioning on the current value estimates givesThus the sample error has the correct mean direction for correcting the current Bellman mismatch. The defining idea is bootstrapping: a later prediction supplies part of the earlier prediction's target, so learning need not wait for a final outcome.^[ref]

In tabular temporal-difference policy evaluation, convergence requires appropriate sampling and step sizes, not merely writing the update. Standard sufficient conditions include bounded rewards, infinitely many visits to each relevant state and, along visits to each state, ${\sum }_t{\alpha }_t(s)=\infty$ with ${\sum }_t{\alpha }_t(s{)}^2<\infty$. Diminishing steps allow continuing correction while limiting accumulated sampling noise. Constant steps generally track a noisy estimate instead of converging exactly. The target's dependence on the present values also means that this is not ordinary gradient descent on an independent, fixed supervised label. These tabular guarantees should not be transferred automatically to nonlinear function approximation or off-policy training.

For an exact illustrative problem, alternate deterministically between states $A$ and $B$, receive reward $1$ on leaving $A$ and $0$ on leaving $B$, and take $\gamma =1/2$. ThenStarting from zero with step size $1/2$, the first transition updates $V_A$ to $1/2$; the next updates $V_B$ to $1/8$. At the exact solution, both transition errors are zero. These values are a model calculation, not neural measurements.

This solves evaluation of the specified policy. The optimal Bellman equation instead maximizes over possible actions. An intelligent agent can combine policy evaluation with policy iteration or an actor-critic improvement mechanism. Estimating the value of a poor fixed policy does not by itself make that policy optimal. Episodic tasks use terminal-state value zero; undiscounted continuing tasks require additional conditions or a different formulation.

A proposed neural implementation uses a representation of the situation to drive a value-predicting population, with a reward prediction error modulating recently active synapses. An eligibility trace can preserve a record of prior activity so delayed errors influence earlier states. Temporal representation is indispensable: if the population does not distinguish when a reward is expected, it cannot generate the appropriate omission signal at that time.

Primate recordings during acquisition of successive delayed-response tasks found that dopamine-neuron reward responses were more prominent during learning than after performance was established, while significant cues elicited phasic responses. This supports prediction-sensitive signalling but also allows attentional and motivational contributions.^[ref] The temporal-difference interpretation explains how a reward response can diminish as reward becomes predicted and a response can develop at an informative cue; a worse-than-expected omission gives a negative error. The physiological interpretation is a quantitative hypothesis, not an identification of every dopamine signal with a single critic variable.^[ref]

Causal evidence comes from reward-timed stimulation of dopamine neurons in rat blocking and extinction tasks. Artificial activation, intended to supply a positive prediction-error-like event, increased subsequent cue-driven reward seeking. This strengthens the teaching-signal interpretation beyond response correlation. It does not show that all components of the Bellman computation reside in dopamine neurons or that the entire algorithm is unique.^[ref]

A world model supports intelligent behaviour by predicting the consequences of actions that need not be executed first. The prefrontal cortex can contribute task-state and goal control, while the hippocampus can supply relational and episodic content for constructing possible situations and trajectories. This is a division of computational requirements, not a rigid one-region-per-function scheme.

In a Markov decision process, a model can represent transitions $\hat{P}(s^{\prime }\mid s,a)$ and expected rewards $\hat{r}(s,a)$. Planning uses them to evaluate an action through a backup such asLonger searches apply the same principle across alternative trajectories. A world model can be symbolic, distributed, probabilistic or a combination; it need only preserve information relevant to the decision. In a partially observed situation, the intelligent agent must infer a state or maintain uncertainty over states rather than treating the latest image as a complete description of the world.

For a simple constructed example, suppose one action leads to food and another to water, with current outcome values $2$ and $1$. After the food is devalued to $0$, an intelligent agent that knows the action–outcome relations can immediately prefer water without experiencing the food-producing action again. A purely cached action value does not necessarily change at that moment. This demonstrates the usefulness of an internal model; it does not imply that every devaluation effect uniquely identifies one algorithm, because inferred state changes or offline value updates can also alter cached decisions.

Mental simulation can recombine remembered components into a possible future, evaluate an untried route and compare goals. It differs from simply replaying a previous trajectory verbatim. It also differs from episodic memory retrieval: simulated content may describe something that never happened. Both operations can use shared representations, so a new imagined situation need not be generated independently of memory.

The prefrontal cortex is well placed to contribute the control side of this process: maintaining the current task, selecting relevant information, representing goals and using prospective outcomes to guide action. It is heterogeneous, and activity in one subregion is not evidence that all of prefrontal cortex carries a complete internal simulator. A particularly relevant hypothesis concerns the orbitofrontal cortex: a useful decision state may depend on previous events and task rules even when current sensory input is unchanged.

A human fMRI study used superimposed face and house images with a rule determining which category to judge from the preceding task history. Different hidden task states could therefore accompany similar current inputs. Cross-validated multivariate decoding recovered task-state information from orbitofrontal cortex, and decoding fidelity related to behavioural accuracy. This supports a role in representing the situation in which values and actions are evaluated. It does not demonstrate that the decoded patterns themselves contain a complete future trajectory, and noninvasive imaging cannot identify the synaptic algorithm.^[ref]

The hippocampus provides a complementary source of spatial and relational content. A cognitive map describes relationships among locations or task states rather than only a sequence of rewarded responses. Such a representation can support a novel route when goals change, and event representations can contribute objects, locations and contextual relations to a simulated scene. Whether an internally generated sequence represents a possible future, a remembered past or a training signal must be tested rather than inferred from sequence-like firing alone.

In freely moving rats choosing journeys between food locations, hippocampal place-cell ensembles sometimes produced internally generated sequences before travel. Decoded sequences described trajectories related to remembered goals and predicted upcoming behaviour. The ordering and timing make the result relevant to prospective computation, but the recording is correlational: a sequence could reflect a prepared choice or goal-related retrieval rather than perform the decisive search itself.^[ref]

A separate intervention interrupted awake sharp-wave ripples during a spatial alternation task and impaired learning and performance. Place fields and post-experience reactivation were relatively preserved, helping distinguish the effect from wholesale destruction of spatial coding or later replay. This supports a causal contribution of awake ripple-associated processing to memory-guided decisions, without identifying every disrupted sequence as a planning calculation.^[ref]

Human lesion evidence extends the discussion beyond navigation. Patients with predominantly bilateral hippocampal damage were asked to construct new experiences from short scenario cues. Their descriptions were generally less spatially coherent than those of matched controls, despite preserved semantic retrieval; one patient performed well. The task therefore supports a hippocampal contribution to binding imagined scene elements, while the spared case, lesion selectivity and the difference between scene construction and action planning limit a universal necessity claim.^[ref]

A plausible integrated model lets prefrontal representations specify the task and current goal, hippocampal and cortical representations generate or retrieve candidate situations, and valuation and action-selection circuits compare their consequences. Communication can be iterative: candidate outcomes change what information is sought, and new observations update the inferred state. This is more specific than assigning “imagination” to the hippocampus and “intelligence” to prefrontal cortex, but remains a hypothesis about their interaction.

Planning also has costs. Long simulations can amplify model errors, and unlimited search is computationally expensive. An intelligent agent should select a useful abstraction, prioritize relevant branches and decide when a cached policy is adequate. Tests should distinguish sensitivity to reward changes from sensitivity to transition changes, and compare neural predictions before a decision rather than only after a successful action. World models enable flexible prospective control; the evidence implicates interacting state, memory and valuation processes, rather than a single anatomical seat of mental simulation.

A time-homogeneous Markov decision process specifies a state space, admissible actions at each state, an action-dependent transition kernel and one-step reward, with neither kernel nor reward depending on time. A policy chooses actions using the observed history. The positive programming case has nonnegative rewards and maximizes expected undiscounted total reward, allowing infinite values; its finite-horizon values increase to the infinite-horizon supremum under the appropriate approximation argument.

Here let ${\tau }_B$ be the absorption time of the underlying simple random walk at $0,N$. Every admissible stopping time $T$ is at most ${\tau }_B$. The reward is bounded by $R_{\max }={\max }_{j}r(j)$, and $E_i{\tau }_B=i(N-i)$, as follows by solving $h_i=1+(h_{i-1}+h_{i+1})/2$ with zero endpoint values. In particular absorption is almost surely finite. Truncating any policy at $T\wedge n$ changes its reward expectation by at most $2R_{\max }{P}_i({\tau }_B>n)\le 2R_{\max }i(N-i)/n$. Since the truncated policy is allowed in the $n$-step problem,This proves $V_n\to V$, even uniformly on the finite state space.

The finite-horizon recursion starts with $V_0=r$, fixes the endpoint rewards and hasTaking limits shows $V\ge r$ and $2V(i)\ge V(i-1)+V(i+1)$, so $V$ is discretely concave. If $W$ is any concave function majorizing $r$, induction in this same recursion gives $V_n\le W$, and hence $V\le W$. Therefore $V$ is the smallest concave majorant of the rewards. At a point where $V(i)>r(i)$ the recursion forces equality with the neighboring average; the value graph is linear through each consecutive continuation region.

An optimal policy stops upon first entering the contact set $\{i:V(i)=r(i)\}$ and continues elsewhere. Before stopping the neighboring-average equality makes $V$ of the walk a bounded martingale; the stopping time is bounded by ${\tau }_B$. Applying the bounded stopping identity by first truncating the time and then passing to the limit proves the expected terminal reward equals $V(i)$.

Distinct rewards do not guarantee uniqueness. With $N=2$ and $r(0)=0,r(1)=1,r(2)=2$, the reward function is already linear and $V=r$. From state one, stopping gives one, while continuing to the next step also gives expected reward $(0+2)/2=1$. Both policies are optimal. Thus the claimed uniqueness is false even when all rewards are distinct.