Planning and acting in partially observable stochastic domains

Reference: Kaelbling, L.P., Littman, M.L. & Cassandra, A.R. (1998). Planning and acting in partially observable stochastic domains. Artificial Intelligence 101(1–2), pp. 99–134. Elsevier. DOI: 10.1016/S0004-3702(98)00023-X. (Brown University; Duke University; Microelectronics and Computer Technology Corporation.) URL.

Summary

The paper opens with a robot navigating an office building whose actions are unreliable (it overshoots turns, fails to move) and whose observations are ambiguous (a corridor looks like a corner, a T-junction like an L-junction). Kaelbling, Littman and Cassandra state two intentions: to recapitulate work from the operations-research literature and connect it to closely related work in AI, and to describe a novel algorithm for solving POMDPs exactly. They begin from the Markov Decision Process, the tuple ⟨S, A, T, R⟩ in which the agent has “complete and perfect perceptual abilities” — great uncertainty about the effects of actions, none about the current state — and review value iteration and the Bellman Equation for it. A POMDP relaxes exactly the perceptual assumption: the tuple becomes ⟨S, A, T, R, Ω, O⟩, adding a finite observation set and an observation function O : S × A → Π(Ω), so the agent “makes an observation based on the action and resulting state” rather than seeing the state itself. Mapping the most recent observation directly to an action is dismissed — in the hallway example “this amounts to performing the same action in every location that looks the same”; randomised observation-action mappings do somewhat better, but acting effectively requires memory of previous actions and observations.

The framework’s central move is to decompose the agent into a state estimator SE and a policy π defined over the estimator’s output. The output is a belief state b, a probability distribution over S, updated by Bayes’ rule: b'(s') = O(s', a, o) Σ_s T(s, a, s') b(s) / Pr(o | a, b). The most probable state will not do; an agent must take account of its own degree of uncertainty in order to know when to seek out a landmark or read a sign. Belief states “comprise a sufficient statistic for the past history and initial belief state of the agent”: given a correctly computed belief state, no further data about past actions or observations would say anything more about the current world state, or increase expected reward. Hence the process over belief states is Markov, and the policy problem becomes a continuous-space belief MDP ⟨B, A, τ, ρ⟩ with ρ(b, a) = Σ_s b(s) R(s, a). The apparent oddity of rewarding an agent for believing it is in good states is answered directly: because SE is built from a correct model, b represents the true occupation probabilities, so ρ is the true expected reward. A crucial consequence of the formulation is that no distinction is drawn between actions that change the world and actions that gain information: “in general, every action has both types of effect,” and optimal behaviour becomes something akin to a value-of-information calculation, only more complex.

Solving that continuous MDP exploits its geometry. A t-step nonstationary policy is a policy tree; its value in belief state b is V_p(b) = b · α_p, linear in b, where α_p collects the tree’s values at each world state. The optimal t-step value function is the upper surface of these hyperplanes, V_t(b) = max_{p∈P} b · α_p, and is therefore piecewise-linear and convex — convexity making intuitive sense, since high-entropy belief states in the middle of the simplex leave the agent unable to select actions appropriately. Only a minimal parsimonious subset of vectors is needed, and projecting the value function back down partitions belief space into polyhedral regions with one dominant policy tree each. The simplest exact algorithm, exhaustive enumeration (Monahan; Smallwood and Sondik), generates a superset of |A||V_{t-1}|^{|Ω|} policy trees before pruning by linear programming — always exponential in |Ω|, however small V_t turns out to be. The paper’s contribution, the Witness algorithm, instead computes a separate Q-function Q_t^a for each action, then unions and prunes. Its inner loop repeatedly asks whether some belief state — a witness — exists at which the true Q_t^a(b) differs from the current approximation; the witness theorem (Theorem A.1, proved in Appendix A) establishes that such a point exists if and only if some policy tree in the current set can be improved by replacing a single subtree, which reduces the search to a linear program. Witness runs in time polynomial in |S|, |A|, |Ω|, |V_{t-1}| and Σ_a |Q_t^a|. The authors are careful about what this does and does not buy: the Q_t^a may be exponentially larger than V_t, “though this seems to be rarely the case in practice,” and an algorithm polynomial in |V_t| itself is not sought, because its existence “would settle the long-standing complexity-theoretic question ‘Does NP = RP?’ in the affirmative.” Cheng’s linear support algorithm can be viewed as a variant of Witness seeking witnesses at region corners, and families of POMDPs exist that Cheng’s algorithm solves in polynomial time but Witness takes exponential time to solve.

The paper then illustrates policy structure on the tiger problem (listen at cost −1 with accuracy 0.85, open the correct door for +10, the wrong one for −100). The optimal 2- and 3-step policies never open a door at all, only listen, since opening resets belief to (0.5, 0.5). Under discounting the situation-action mappings converge; for the tiger problem the graph structure first appears at t = 56 and remains constant through t = 105, whereupon algorithmic precision can no longer distinguish successive vectors. Where the infinite-horizon value function is finitely transient the resulting stationary policy can be redrawn as a plan graph — “essentially a finite-state controller,” using the minimal memory needed to act optimally, and extractable automatically from two successive equal value functions, with no explicit belief state maintained on line. In general, however, the infinite-horizon discounted value function remains convex but “may have infinitely many facets,” and can only be approximated. The concluding sections are frank about the limits. The methods require states to be enumerated rather than represented compositionally (via Bayes nets or probabilistic operators). Experimental results are cited to the effect that “even the witness algorithm becomes impractical for problems of modest size (|S| > 15 and |Ω| > 15),” and the authors point to their own then-current work on function approximation and simulation focused on frequently visited parts of belief space, which yielded a very good solution to an 89-state, 16-observation hallway navigation problem. Acquiring the world model is explicitly not addressed. A closing observation: there exist infinite-horizon POMDPs for which no finite-state plan suffices — simple 2-state examples require counting — so that “in the limit, a plan is actually a program.”

Key Ideas

POMDP = MDP + observation function: ⟨S, A, T, R, Ω, O⟩, where O : S × A → Π(Ω) gives, for each action and resulting state, a distribution over observations. The agent’s goal remains maximising expected discounted future reward.
Agent decomposes into SE + π: a state estimator maintaining a belief state, and a policy mapping belief states — not world states — to actions.
Belief state as sufficient statistic: a distribution over S, updated by Bayes’ rule from the previous belief, the last action and the current observation. Given it, no further data about the past improves expected reward; the process over belief states is Markov.
Most-probable-state is not enough: to act well an agent must represent its own uncertainty, since that is what licenses information-gathering actions.
No privileged information-gathering actions: the POMDP framework draws no distinction between acting to change the world and acting to gain information; every action generally does both, and their informational properties are carried entirely by O.
The belief MDP: a continuous-state MDP ⟨B, A, τ, ρ⟩ with ρ(b, a) = Σ_s b(s) R(s, a). An optimal policy for it, coupled with a correct state estimator, is optimal for the original POMDP.
Policy trees and α-vectors: a t-step nonstationary policy is a depth-t tree branching on observations; its value V_p(b) = b · α_p is linear in the belief state.
Piecewise-linear convex value function: V_t(b) = max_{p∈P} b · α_p is the upper surface of the policy trees’ hyperplanes. Convexity reflects that high-entropy beliefs afford worse action selection — a connection to value of information. Projecting V_t down partitions belief space into polyhedral regions, each with one dominant tree.
Parsimonious representation: most policy trees are dominated; a unique minimal set of “useful” vectors represents the same value function, found by pruning with linear programs (Sondik’s simple test; Lark and White’s more efficient method).
Exhaustive enumeration is exponential in |Ω|: it builds a superset of |A||V_{t-1}|^{|Ω|} trees before pruning, regardless of how small V_t is.
The Witness algorithm: compute a parsimonious Q_t^a per action, then union and prune to get V_t. Runs in time polynomial in |S|, |A|, |Ω|, |V_{t-1}| and |Q_t^a| — the primary complexity-theoretic difference from prior exact methods, which can run exponentially in |Q_t^a|.
The witness theorem (Thm A.1): the approximate and true Q-functions differ iff some tree in the current set can be improved at some belief state by replacing exactly one subtree — reducing witness-finding to a linear program.
A deliberate non-goal: an algorithm polynomial in |S|, |A|, |Ω|, |V_{t-1}| and |V_t| is not pursued, since its existence would settle “Does NP = RP?” in the affirmative.
No exact method dominates: Cheng’s linear support algorithm is a Witness variant seeking witnesses at region corners, efficient in very small state spaces; families of POMDPs exist that it solves in polynomial time and Witness does not. Zhang and Liu’s incremental pruning is empirically faster while sharing Witness’s worst-case complexity.
Infinite horizon: the discounted optimal value function stays convex but may have infinitely many facets; it is approximated arbitrarily well by a sufficiently long finite horizon.
Plan graphs as finite-state controllers: where the optimal policy is finitely transient, the converged policy can be redrawn as a plan graph that acts optimally with minimal memory and no on-line belief state. There is no known a priori bound on its size — degrading the tiger problem’s listening reliability from 0.85 to 0.65 forces a much larger graph.
A plan is, in the limit, a program: some infinite-horizon POMDPs admit no finite-state optimal plan (2-state examples requiring counting); pushdown automata or Turing machines may be needed in general.
Stated limits: states are represented enumeratively, not compositionally; exact solution is impractical beyond roughly |S| > 15 and |Ω| > 15; model acquisition is not addressed.

Connections

Conceptual Contribution

Claim: An agent that cannot observe the world’s state can still act optimally by maintaining a probability distribution over states — a belief state — which is a sufficient statistic for its entire history of actions and observations. Planning under partial observability therefore reduces, without loss, to solving a fully observable MDP over the continuous space of belief states; and although that space is continuous, the optimal finite-horizon value function over it is piecewise-linear and convex, so it admits exact finite representation and exact solution.
Mechanism: Extend the MDP tuple with observations Ω and an observation function O : S × A → Π(Ω). Split the agent into a state estimator (Bayes update of b from ⟨b, a, o⟩) and a policy over belief states. Lift T and R to a belief MDP ⟨B, A, τ, ρ⟩. Represent each t-step nonstationary policy as a policy tree p whose value is the linear function b · α_p; the optimal V_t is the upper surface of these, hence PWLC, and only a parsimonious subset of α-vectors is needed. Compute V_t by value iteration, avoiding the |A||V_{t-1}|^{|Ω|}-sized superset of exhaustive enumeration: the Witness algorithm builds each action’s Q_t^a incrementally, using a linear program to hunt for witness belief states at which the current approximation is wrong, justified by the witness theorem that any such discrepancy is exposed by a single-subtree replacement. Where the resulting infinite-horizon policy is finitely transient, collapse it into a plan graph — a finite-state controller carrying the minimal memory needed to act optimally.
Concepts introduced/used: POMDP, Belief State, Sufficient Statistic, Bayesian Filtering, Markov Decision Process, Bellman Equation, Value Iteration, Policy Tree, Piecewise-Linear Convex Value Function, Witness Algorithm, Plan Graph, Finite-State Controller, Value of Information
Stance: formal framework synthesis plus novel exact algorithm (operations-research theory imported into AI planning, with worked examples and cited empirical comparison; no large-scale empirical study)
Relates to: Supplies the formal object that Interpreting Systems as Solving POMDPs later takes as its criterion for agency — the belief state, belief-state MDP, Bellman optimal value function and optimal policy that Biehl and Virgo ask a physical system’s dynamics to be consistent with. Recasts the classical-planning problem of Programs with Common Sense and Some Philosophical Problems from the Standpoint of Artificial Intelligence in decision-theoretic rather than logical terms, replacing knowledge preconditions and epistemic logic with probability distributions that admit gradations of knowledge, an expressiveness the authors contrast explicitly with three-valued and known/unknown representations and with the epistemic logics of Reasoning About Knowledge. Its state estimator is the discrete counterpart of the Kalman Filter the introduction rejects as unable to represent multimodal spatial uncertainty. Its insistence that memory of past actions and observations is indispensable — that mapping current observation to action “amounts to performing the same action in every location that looks the same” — is a direct decision-theoretic reply to the reactive, memoryless architectures of Intelligence Without Representation and A Robust Layered Control System. Its closing observation that a plan is, in the limit, a program echoes the identification of plan structure with computational structure in Algorithm = Logic + Control.

Backlinks

Linked Pages

Algorithm = Logic + Control

Reference

Kowalski, R. (1979). “Algorithm = Logic + Control.” Communications of the ACM, 22(7), 424-436. URL

Summary

Kowalski argues that every algorithm can be cleanly decomposed into two orthogonal components: a logic component, which specifies what knowledge is to be used to solve the problem, and a control component, which specifies how that knowledge is applied. The logic determines meaning and correctness; the control determines efficiency. The thesis is that programs become easier to write, to prove correct, and to optimize when these two concerns are separated and each is expressed explicitly — ideally, with the logic invariant under changes in control strategy.

Using Horn clauses as the logical language, Kowalski shows that a problem’s specification (e.g., “x is an ancestor of y”) can be written once and then executed under different control regimes — top-down (backward chaining, as in Prolog) or bottom-up (forward chaining, as in database query evaluation) — without changing the logic. Different strategies produce different computational costs, but all produce the same answers because the meaning is governed by the logic alone. He illustrates with factorial, sorting, and path-finding, and crucially with Horn-clause definitions of recursive relations where choice of control dramatically affects termination and performance.

The paper is the manifesto of logic programming. It frames Prolog not as “predicate logic with a goto button” but as one control discipline over a logical program; it underwrites deductive databases, constraint logic programming, tabled evaluation, and answer-set programming; and it anticipates the modern separation of declarative specification from execution plan found in SQL optimizers, datalog engines, and differentiable programming. The slogan “A = L + C” remains a litmus test: a program whose logic and control are tangled is harder to understand than one where they are kept apart.

Key Ideas

A = L + C: an algorithm has a logic component (meaning) and a control component (execution strategy).
Logic determines correctness; control determines efficiency: change control without changing meaning.
Horn clauses: clausal form of predicate logic sufficient for programming, with tractable inference.
Top-down vs bottom-up: backward-chaining (SLD resolution / Prolog) and forward-chaining (datalog / bottom-up) as control choices.
Declarative programming: say what is true; let a general-purpose inference mechanism search for solutions.
Separation of concerns: specifications, programs, and query plans all viewable through the same lens.
Clausal refutation: problems stated as denials, solved by deriving contradiction, answer extracted from substitutions.

Connections

Foundations of Logic Programming - Lloyd — Lloyd’s book formalizes the semantics Kowalski sketches.
Logicist AI
Horn Clauses
A Universal Modular Actor Formalism for Artificial Intelligence — PLANNER had a similar logic/control split that Kowalski clarifies.
Code as Data — logic programs are homoiconic data usable by other programs.

Conceptual Contribution

A Robust Layered Control System

A Robust Layered Control System for a Mobile Robot

Reference: Brooks, R. A. (1986). A Robust Layered Control System for a Mobile Robot. IEEE Journal of Robotics and Automation, 2(1), pp. 14–23. (Originally MIT AI Lab Memo 864, September 1985.) IEEE DOI · Open access PDF (MIT AI Memo 864)

Summary

Brooks introduces the subsumption architecture — a radical alternative to the sense-plan-act paradigm that dominated robotics through the 1980s. Where the prevailing approach decomposed robot control into functional modules (perception, world modelling, planning, motor control) operating on a single shared symbolic representation, Brooks’s architecture decomposes by behaviour: each layer of the system is a complete sense-act loop implementing one behavioural competence (avoid obstacles, wander, explore, build maps, identify objects, plan, …). Layers run concurrently and are connected by suppression and inhibition wires that allow higher (later-built) layers to subsume the outputs of lower layers. The lowest layer alone produces a useful (if minimal) robot — an obstacle-avoiding wanderer; each additional layer adds more sophisticated competence on top of an already-functional system. There is no central representation, no shared world model, no symbolic planner driving low-level action. Brooks demonstrated the architecture on a real mobile robot (Allen, the AI Lab’s first subsumption-architecture robot) navigating a cluttered office environment in real time — performance unattainable by the symbolic-AI robots of the era. The 1986 paper is the formal architecture description; the underlying philosophical thesis — that intelligent behaviour does not require explicit representation, that the world is its own best model — is developed in the 1991 follow-ups Intelligence Without Representation and Elephants Don’t Play Chess. The subsumption architecture inaugurated behaviour-based robotics as a research programme, influenced multi-agent systems through the reactive vs deliberative agents distinction, and supplied a substantial counter-tradition to BDI-style symbolic agency.

Key Ideas

Decomposition by behaviour, not function: each layer is a complete sense-act loop implementing one behavioural competence; functional decomposition (perception / planning / control) is rejected as the wrong organising principle.
Layered competence: layer 0 is a working (minimal) robot; each subsequent layer adds capability on top of an already-running system. The N-layer system always behaves at least as well as the (N-1)-layer system.
Suppression and inhibition wires: inter-layer communication is by suppression (a higher layer’s output replaces a lower layer’s signal at the suppression node for a fixed time) and inhibition (a higher layer’s signal blocks a lower layer’s output without substituting). No higher-bandwidth representation passes between layers.
No central representation: there is no shared world model. Each layer maintains its own state as needed; cross-layer communication is restricted to the suppression/inhibition primitive.
The world is its own best model: rather than maintain symbolic representations of the world, the robot perceives the world directly when it needs to act on it. Eliminates the symbol-grounding problem and the cost of keeping a world model synchronised with reality.
Real-time, real-environment demonstration: the architecture was demonstrated on Allen, then Herbert, then later the Cog humanoid project — operating in real environments in real time, with performance that the dominant symbolic-AI robotics could not match.
Modular evolution-friendly architecture: layers can be added or removed without modifying others; the architecture is robust to layer failure (the next-lower layer continues to operate). Brooks frames this as an evolutionary architecture in which more sophisticated competences accrete on top of basic survival competences.

Connections

Conceptual Contribution

Claim: Intelligent robot behaviour can be built by decomposing along behavioural competence rather than functional modules: each layer is a complete sense-act loop, layers run concurrently, higher layers subsume lower ones via suppression/inhibition, and there is no central symbolic representation. The architecture is incremental, evolution-friendly, and demonstrably outperforms symbolic-AI robotics in real-time real-world tasks.
Mechanism: Concurrent finite-state-machine layers each implementing one behavioural competence; suppression nodes (replace) and inhibition nodes (block) for inter-layer interaction; no shared world model; demonstration on real mobile robots (Allen, Herbert) in real environments.
Concepts introduced/used: Subsumption Architecture, Behaviour-Based Robotics, Reactive vs Deliberative Agents (the dichotomy this paper inaugurated), Suppression / Inhibition Networks, Layered Competence, Embodiment.
Stance: systems-engineering paper / programmatic break with symbolic-AI orthodoxy.
Relates to: Inaugurates the reactive (or behaviour-based) tradition in agent architectures, opposed at the time to the deliberative / symbolic tradition that produced BDI agents (Rao & Georgeff 1991, Cohen & Levesque 1990) and Agent-Oriented Programming (Shoham 1993). The dichotomy is now mostly resolved as a layered hybrid (3T architecture, BDI with reactive lower layers), but the historical break drove the conceptual repertoire of MAS for two decades. Conceptually adjacent to The Society of Mind (Minsky 1986) — both treat intelligence as the cooperation of many simple specialised agents, though Minsky’s society of agents are still symbolic where Brooks’s subsumption layers are not. The 1991 follow-ups Intelligence Without Representation (already in vault as Intelligence Without Representation) and Elephants Don’t Play Chess extend the philosophical critique. In modern multi-agent systems, the reactive vs deliberative distinction underwrites the design of LLM-agent architectures: the contemporary debate over chain-of-thought / planner-decoupling / tool-use vs end-to-end-trained reactive agents recapitulates Brooks’s polemic with new vocabulary.

Reference

Brooks, Rodney A. (1991). “Intelligence without representation.” Artificial Intelligence 47: 139–159. (Received September 1987.)
PDF: people.csail.mit.edu/brooks/papers/representation.pdf
Local: brooks1991_representation.pdf

Summary

Brooks challenges the dominant symbol-manipulation paradigm of classical AI, arguing that “representation is the wrong unit of abstraction in building the bulkiest parts of intelligent systems.” Drawing on an evolutionary argument — 3.5 billion years were spent evolving sensorimotor and survival competence, and only a few thousand years on “expert” symbolic knowledge — he claims the hard part of intelligence is mobility, vision, and acting in dynamic environments, not the formal problem-solving that dominated early AI. The “blocks-world” style of AI succeeds only because researchers have already factored out perception and motor action, relegating them to input/output black boxes.

In place of centralized symbolic architectures, Brooks proposes building autonomous mobile robots he calls “Creatures,” decomposed by activity rather than by function. Each activity-producing layer connects sensing to action directly and runs in parallel; higher layers are incrementally added on top of lower, already-working layers without a central symbolic world model. This is the subsumption architecture. The slogan is “the world is its own best model”: rather than maintaining an internal representation the robot re-perceives what it needs.

The paper’s philosophical payload is a rejection of the sense–model–plan–act pipeline and of the assumption that intelligence can be decomposed into modules trading symbolic messages. Brooks argues this methodological commitment — that perception delivers a human-style Merkwelt that central reasoning can operate on — is a form of self-deception, since each species and each robot inhabits its own Merkwelt. Intelligence is to be built bottom-up, situated and embodied, tested continuously against the real world.

Key Ideas

Situatedness and embodiment as design primitives: Creatures must cope with a dynamic environment and have some purpose in being.
Decomposition by activity, not function: layers of task-achieving behavior (avoid, wander, explore) replace perception → modeling → planning → action pipelines.
Subsumption architecture: higher competence layers inhibit/subsume lower ones while lower continue running.
No central representation: “the world is its own best model”; no shared symbolic world model between layers.
Evolutionary time argument: sensorimotor intelligence is the hard, ancient core; symbolic expertise is a thin late veneer.
Critique of abstraction: abstracting away perception and action is how AI self-deceives about having solved problems.
Hypothesis (H): representation is the wrong primitive for building intelligent systems.

Connections

Subsumption Architecture — this paper is the manifesto.
Intelligent Agents Theory and Practice — Wooldridge & Jennings use Brooks as the exemplar of reactive agents, contrasted with deliberative BDI agents.
The Society of Mind — shares the anti-monolithic, many-small-agents intuition, though Minsky retains representations.
Multi-Agent Systems — reactive/behavior-based approaches feed directly into swarm and MAS work.
Actor Model — independent parallel activity producers without a central controller.
A Universal Modular Actor Formalism for Artificial Intelligence — kindred rejection of centralized control.
Agent Architecture — subsumption is a canonical architecture contrasted with BDI, layered, hybrid.
Contrast with Knowledge Representation, Ontologies, Advice Taker — papers that double down on representation.

Conceptual Contribution

Kalman Filter

(page does not exist)

Reasoning About Knowledge

Reference: Fagin, Ronald; Halpern, Joseph Y.; Moses, Yoram; & Vardi, Moshe Y. (1995). Reasoning About Knowledge. MIT Press, Cambridge, MA. 477 pp. ISBN 0-262-06162-7 (cloth, 978-0-262-06162-9); paperback ed. 2003 (978-0-262-56200-3). Publisher: https://mitpress.mit.edu/9780262061629/reasoning-about-knowledge/.

Summary

Reasoning About Knowledge is the standard graduate reference for the modal logic of knowledge and its application to multi-agent and distributed systems. Its central object is the operator K_i (“agent i knows”), interpreted over possible-worlds (Kripke) semantics: an agent knows a fact φ exactly when φ holds in every world it considers possible. The accessibility relation that fixes which worlds are “considered possible” is an equivalence relation, yielding the system S5 — knowledge is truthful (the T axiom), and positively and negatively introspective (the 4 and 5 axioms) — which the authors contrast with weaker logics for belief (KD45) and with notions appropriate to resource-bounded reasoners.

The book’s distinctive contribution is the runs-and-systems (interpreted systems) framework, which grounds this abstract logic in concrete computation. A run is a complete history of a multi-agent system over time; a point is a (run, time) pair; an agent’s local state determines which global points it cannot distinguish, and that indistinguishability relation is the epistemic accessibility relation. Knowledge thereby becomes an objective, ascribed property of a system’s information flow — “agent i knows φ” means φ holds at every point i cannot tell apart from the actual one — rather than a claim about anyone’s mental state. On this base the authors build the hierarchy of group knowledge: everyone-knows (E), common knowledge (C, the infinite fixpoint E^ω), and distributed/implicit knowledge (D, what the group would know by pooling). Worked epistemic puzzles — the muddy children, the coordinated-attack / two-generals problem — show why common knowledge is necessary for simultaneous coordinated action yet unattainable by message exchange in asynchronous systems, recovering the impossibility result of the authors’ own Knowledge and Common Knowledge in a Distributed Environment as a special case.

The later chapters develop the engineering payoff and the hard problems. Knowledge and time are combined into logics whose completeness and (often very high) complexity the authors chart precisely. Knowledge-based programs specify agent behaviour in terms of tests on knowledge (“if you do not know that the channel is clear, resend”), giving an implementation-independent way to design and verify protocols. Finally the book confronts logical omniscience — the unrealistic prediction of S5 that agents know all logical consequences of their knowledge — and surveys remedies: explicit-vs-implicit knowledge via awareness, local reasoning (non-omniscient societies of sub-agents), and impossible/non-standard worlds. The result is a unified treatment spanning AI, distributed computing, game theory, and philosophy.

Key Ideas

Knowledge as possible-worlds quantification: K_i φ holds iff φ is true in every world i considers possible; the logic of an equivalence accessibility relation is S5 (axioms K, T, 4, 5).
Interpreted systems / runs-and-systems: an agent’s indistinguishability over global histories defines its knowledge — an ascribed, externalist account requiring no mentalistic commitment.
Group-knowledge hierarchy: implicit/distributed knowledge D ⊒ everyone-knows E ⊒ common knowledge C; C is the fixpoint needed for simultaneous action.
Muddy children & coordinated attack: canonical puzzles showing how public announcement creates common knowledge and why no finite message chain can in asynchronous settings.
Knowledge and time: epistemic + temporal logics, with completeness axiomatisations and sharp complexity bounds (often PSPACE-complete to non-elementary).
Knowledge-based programs: protocol specifications written against knowledge tests, separating what an agent must know to act from how it represents that knowledge.
Logical omniscience and its cures: awareness operators, explicit vs implicit knowledge, local reasoning, and non-standard worlds for resource-bounded agents.
Belief vs knowledge: dropping veridicality (T) gives KD45 belief; the framework cleanly parameterises the modal strength to the application.

Connections

Knowledge and Common Knowledge in a Distributed Environment — the 1990 Halpern–Moses paper this book generalises and systematises.
Epistemic Logic
Epistemic S5
Common Knowledge (Convention) — the same E^ω construction shared with Lewis and Aumann.
Convention - Lewis
The Synthesis of Digital Machines with Provable Epistemic Properties — Rosenschein & Kaelbling compile exactly this ascribed-knowledge semantics into machines.
The Knowledge Level — Newell’s knowledge-level ascription is the AI sibling of the interpreted-systems stance.
Intention Is Choice with Commitment — Cohen & Levesque’s BDI logic layers belief/goal modalities on this same possible-worlds machinery.
Impossibility of Distributed Consensus with One Faulty Process — FLP has an epistemic reading: common knowledge of a decision is unattainable.
Time Clocks and the Ordering of Events in a Distributed System — Lamport’s local histories underpin the indistinguishable-runs semantics.
Multi-Agent Systems
Possible Worlds Semantics, Kripke Structure, Interpreted Systems, Distributed Knowledge, Knowledge-Based Programs, Logical Omniscience, Muddy Children Puzzle

Conceptual Contribution

Claim: Knowledge in a multi-agent system is not a private mental fact but an objective, ascribable property of the system’s information flow: agent i knows φ exactly when φ holds at every global state i cannot distinguish from the actual one. With this externalist move, the full modal logic of knowledge (S5), group knowledge, and knowledge-over-time become rigorous, computable tools for specifying and verifying distributed and multi-agent protocols.
Mechanism: Possible-worlds (Kripke) semantics with an equivalence accessibility relation, grounded operationally in the runs-and-systems / interpreted-systems model; a group-knowledge hierarchy (D ⊒ E ⊒ C); combined knowledge-and-time logics with completeness and complexity results; knowledge-based programs as implementation-independent protocol specs; and awareness / local-reasoning constructions to escape logical omniscience.
Concepts introduced/used: Epistemic Logic, Epistemic S5, Possible Worlds Semantics, Kripke Structure, Interpreted Systems, Common Knowledge (Convention), Distributed Knowledge, Knowledge-Based Programs, Logical Omniscience, Muddy Children Puzzle
Stance: formal / foundational textbook (logic + theory)
Relates to: Direct book-length expansion of Knowledge and Common Knowledge in a Distributed Environment; provides the semantic substrate operationalised by The Synthesis of Digital Machines with Provable Epistemic Properties; the modal-logic foundation under BDI agent theory (Intention Is Choice with Commitment) and under the game-theoretic common-knowledge of Convention - Lewis; epistemic counterpart to consensus impossibility (Impossibility of Distributed Consensus with One Faulty Process).

Some Philosophical Problems from the Standpoint of Artificial Intelligence

Reference: John McCarthy and Patrick J. Hayes (1969). “Some Philosophical Problems from the Standpoint of Artificial Intelligence.” In B. Meltzer and D. Michie (eds.), Machine Intelligence 4, Edinburgh University Press, pp. 463-502. Source file: mccarthy-mcchay69.pdf. URL

Summary

The paper that introduces situation calculus, names the frame problem, and divides AI cleanly into an epistemological part (what can in principle be inferred from what is knowable about the world) and a heuristic part (how to search that space efficiently). McCarthy and Hayes argue that a program capable of acting intelligently in the world must have a general representation of the world, and that designing such a representation forces the AI researcher to confront traditional philosophical problems — causality, ability, knowledge, free will, counterfactuals — with unusual rigor, because the representation has to be complete enough to drive actual deduction.

The paper is in four parts. Part 1 is philosophical: metaphysically vs epistemologically adequate representations, a proposed resolution of free will in a deterministic universe (via the existence of alternatives that the agent can bring about in its coarser theory), and a treatment of counterfactuals. Part 2 is the formal core: situations as complete states of the universe, fluents as functions on situations, actions as functions from situation to situation with result(a, s), and a method of constructing first-order sentences true exactly when a strategy achieves a goal. Part 3 surveys open problems, most famously the frame problem: how to state concisely what does not change when an action is performed, without writing an axiom for every (action, fluent) pair. Part 4 reviews philosophical logic in relation to AI.

This is the paper that makes temporal / action reasoning a first-class topic in AI. Its ontology of situations, fluents, actions, and result is the direct ancestor of every subsequent theory of action — STRIPS, event calculus, fluent calculus, BDI temporal logics, ConGolog, planning formalisms, and the temporal backbone of Ensuring Trustworthy and Ethical Behaviour in Intelligent Logical Agents. The epistemological/heuristic distinction is picked up again in Epistemological Problems of Artificial Intelligence (1977) and shapes the methodology of logicist AI.

Key Ideas

Epistemological vs metaphysical adequacy of representations: a representation is epistemologically adequate if an observer can in practice express what they can come to know, not just what is ultimately true.
Situation calculus: situations as complete states, fluents as situation-parametrised functions/predicates (e.g., at(x, s)), actions as functions result(a, s).
The frame problem: stating concisely what is unchanged by an action; a foundational difficulty for any action-based formalism.
The qualification problem (in embryo): actions have open-ended preconditions that cannot all be enumerated — later treated in Circumscription - A Form of Nonmonotonic Reasoning.
can, causes, and knows reduced to first-order formulations over situations and strategies, including strategies with loops and knowledge acquisition.
Free will and counterfactuals reinterpreted via alternative strategies available in an agent’s coarser (epistemologically adequate) theory — not by denying determinism.
Division of AI into epistemological and heuristic parts; the paper concentrates on the former.

Connections

Programs with Common Sense — the 1959 predecessor; this paper repairs its treatment of action and time.
Recursive Functions of Symbolic Expressions and Their Computation by Machine
Epistemological Problems of Artificial Intelligence — continues the epistemological-adequacy programme.
Circumscription - A Form of Nonmonotonic Reasoning — formal answer to the qualification problem raised here.
Ascribing Mental Qualities to Machines
First Order Theories of Individual Concepts and Propositions
Generality in Artificial Intelligence
Towards a Mathematical Science of Computation
Correctness of a Compiler for Arithmetic Expressions
Elephant 2000 - A Programming Language Based on Speech Acts
Common Business Communication Language
Common Sense Reasoning
Knowledge Representation
Non-monotonic Reasoning
Epistemic Logic
The Knowledge Level
The Society of Mind
Frame Problem
Situation Calculus
Ensuring Trustworthy and Ethical Behaviour in Intelligent Logical Agents — A-ILTL’s temporal obligations inherit the situation-calculus transition structure.
BDI — BDI logics (Rao & Georgeff, Cohen & Levesque) build their belief/desire/intention modalities on top of situation-calculus-style branching time.
BDI Logic

Conceptual Contribution

Claim: AI requires an epistemologically adequate representation of the world, which forces the AI researcher to solve philosophical problems (causality, ability, knowledge, counterfactuals, free will) formally; situation calculus — situations, fluents, actions with result(a, s) — provides a first-order representation in which strategies achieving goals can be proved correct.
Mechanism: First-order logic with sorted terms for situations, fluents, and actions; the result function; axioms expressing action effects and successor-state relations; proof-of-strategy construction; explicit treatment of knowledge strategies (plans involving learning what one does not yet know); methodological division of AI into epistemological and heuristic parts.
Concepts introduced/used: Situation Calculus, Fluent, Frame Problem, Qualification Problem, Epistemological Adequacy, Metaphysical Adequacy, Counterfactual, Action Formalism, Planning, Knowing How vs Knowing That.
Stance: foundational
Relates to: Names the frame problem that every subsequent action formalism must address; furnishes the ontology that BDI logics and Ensuring Trustworthy and Ethical Behaviour in Intelligent Logical Agents inherit for their temporal/intentional semantics; sets up the qualification problem that Circumscription - A Form of Nonmonotonic Reasoning later solves; methodologically complements Ascribing Mental Qualities to Machines and First Order Theories of Individual Concepts and Propositions; the epistemological-adequacy criterion reappears explicitly in Epistemological Problems of Artificial Intelligence.

Programs with Common Sense

Reference: John McCarthy (1959). “Programs with Common Sense.” In Proceedings of the Teddington Conference on the Mechanization of Thought Processes, pp. 75-91. London: Her Majesty’s Stationery Office. Reprinted in Marvin Minsky (ed.), Semantic Information Processing, MIT Press, 1968, and in McCarthy’s Formalizing Common Sense (Ablex, 1990). Source file: mccarthy-mcc59.pdf. URL

Summary

The founding manifesto for knowledge representation and for logic-based AI. McCarthy proposes the advice taker — a program that reasons by manipulating sentences in a formal language (essentially predicate calculus), takes in advice in the form of declarative sentences, and deduces its actions from its premises together with imperative sentences about what is wanted. The central criterion he names is that the program “will have common sense” just in case it automatically deduces for itself a sufficiently wide class of immediate consequences of anything it is told and of what it already knows.

The paper distinguishes teaching a machine by imperative sentences (fast, no prior knowledge needed) from teaching by declarative sentences (exploits prior knowledge, robust to order, robust to context changes), and stakes AI on the declarative side. It lists five conditions for human-level intelligence — generality of representation, simple expression of behavior changes, improvability of the improving mechanism, concepts of partial success, and the ability to form reusable subroutines — and then sketches the advice taker as a concrete attempt at the second. The paper closes with a famous worked example: getting from home to the airport, formalised in a predicate-calculus-like language with premises such as at(I, desk), at(desk, home), and action axioms, so that the advice taker can chain them into a plan. A discussion appendix (Bar-Hillel, Oliver Selfridge, Yehoshua Bar-Hillel again, McCarthy’s replies) is one of the earliest recorded methodological debates in AI.

Every subsequent McCarthy paper — Recursive Functions (1960), Situation Calculus (1969), Epistemological Problems (1977), Circumscription (1980), Ascribing Mental Qualities (1979) — is in some sense an attempt to repair, extend, or defend a weakness of the advice-taker programme first stated here. It is also the point of origin for the entire declarative / symbolic tradition that the ACL design literature inherits.

Key Ideas

A program has common sense iff it automatically deduces a sufficiently wide class of immediate consequences of what it is told plus what it already knows.
Knowledge should be represented as sentences in a formal language (predicate calculus), not baked into procedures.
Declarative vs imperative instruction: declarative scales, imperative is fast; the advice taker chooses declarative.
To learn something, a program must first be capable of being told it.
Five pre-conditions for general intelligence: arbitrary behavior representable, simple expressibility of changes, improvable improvement mechanism, partial-success concepts, reusable subroutines.
Worked airport example — the first substantive formalisation of a situated plan in logic.

Connections

Recursive Functions of Symbolic Expressions and Their Computation by Machine — Lisp, the implementation vehicle proposed for the advice taker.
Some Philosophical Problems from the Standpoint of Artificial Intelligence — 1969 elaboration, introducing situation calculus to repair the action formalisation.
Epistemological Problems of Artificial Intelligence — 1977 diagnosis of what has and has not worked.
Circumscription - A Form of Nonmonotonic Reasoning — needed to make advice-taker inference non-monotonic.
Ascribing Mental Qualities to Machines
First Order Theories of Individual Concepts and Propositions
Generality in Artificial Intelligence
Towards a Mathematical Science of Computation
Correctness of a Compiler for Arithmetic Expressions
Elephant 2000 - A Programming Language Based on Speech Acts
Common Business Communication Language
Common Sense Reasoning
Knowledge Representation
The Knowledge Level — Newell’s characterisation of the advice-taker programme as operating at the knowledge level.
The Society of Mind — Minsky’s later (and more sceptical) response to the logicist programme.
Epistemic Logic

Conceptual Contribution

Claim: An intelligent agent can be built by representing its world as sentences in a formal (predicate-calculus) language, letting it take advice in declarative form, and deducing actions as logical consequences of its premises together with sentences about what it wants — the criterion of intelligence being how wide a class of immediate consequences it can automatically derive.
Mechanism: The advice taker architecture: formal-language knowledge base; declarative input (“I am at my desk”); imperative input (“I want to be at the airport”); rules of inference (predicate-calculus-style); action-producing deductions; interaction with humans that add or retract premises.
Concepts introduced/used: Advice Taker, Common Sense Reasoning, Declarative Knowledge, Knowledge Representation, Logicist AI, Planning, Situated Action.
Stance: foundational / programmatic
Relates to: The origin document of the declarative / logicist tradition that Knowledge Representation and Common Sense Reasoning formalise. The advice-taker agenda is continued in Some Philosophical Problems from the Standpoint of Artificial Intelligence (situation calculus to model action), Epistemological Problems of Artificial Intelligence (methodological self-review), and Circumscription - A Form of Nonmonotonic Reasoning (non-monotonicity to handle the qualification problem inherent in declarative advice). Elephant 2000 - A Programming Language Based on Speech Acts and Common Business Communication Language are late-career revivals of the advice-taker vision applied to agent communication.

Interpreting Systems as Solving POMDPs

Interpreting systems as solving POMDPs: a step towards a formal understanding of agency

Reference: Biehl, M. & Virgo, N. (2022). Interpreting systems as solving POMDPs: a step towards a formal understanding of agency. Proceedings of the 3rd International Workshop on Active Inference (IWAI 2022); published in Active Inference. IWAI 2022, Communications in Computer and Information Science, vol. 1721, Springer, Cham. arXiv:2209.01619 (Cross Labs / Cross Compass, Tokyo; Earth-Life Science Institute, Tokyo Institute of Technology). URL.

Summary

When is a physical system entitled to be described as having beliefs and goals? Biehl and Virgo answer with a consistency criterion rather than a predictive one. Their starting point is Dennett’s Intentional Stance, which licenses agent-talk when it out-predicts the Physical Stance. The authors explicitly depart from this comparison-of-stances approach: assuming we already know what the system does at the physical level, they ask whether we can consistently ascribe meaning to its physical states such that those states appear to implement belief updating and decision making. This builds directly on Virgo, Biehl & McGregor’s earlier notion of interpreting a dynamical system as a Bayesian reasoner — something that takes inputs and makes inferences about a hidden variable, but that has neither goals nor actions. The present paper’s contribution is to extend consistent interpretation to cover goals and actions, and thereby to reach agents.

Three deliberate conceptual commitments make this precise. The system is taken to be a stochastic Moore machine (M, I, O, μ, ω) — internal states, inputs, outputs, a stochastic machine kernel, and a deterministic expose function; the authors note this is far from the most general system but is general enough to cover the digital computers running most present-day artificial agents. Beliefs are probability distributions updated in accordance with Bayes’ law. Goals and rationality come from POMDPs, which supply both a formal notion of goal (expected cumulative discounted reward maximisation) and of rational behaviour (the optimal policy). The technical machinery is a consistent Bayesian influenced filtering interpretation (Def. 3): a hidden state space H, an action space A, an interpretation map ψ : M → PH sending machine states to beliefs over hidden states, an action function α : M → A, and a model kernel κ : H × A → P(H × I). A stochastic Moore machine is then interpretable as a solution to a POMDP (Def. 5) if its machine part admits such an interpretation and its expose function emits the optimal action for the belief its state parameterises: ω(m) = π*(ψ(m)). An agent, on this proposal, is the pair of a system and such an interpretation.

Two features do the real work. First, machine states need only parameterise beliefs rather than be belief states — ψ need not be injective, so interpretations come with a built-in notion of coarse-graining, and the definition covers more than the canonical belief-state machines. Proposition 1 shows this is not a loosening in disguise: for any input that is subjectively possible under the interpretation, the parameterised distributions ψ(m) update exactly as the Bayesian belief-state update requires, so V̄*(m) := V*(ψ(m)) is an optimal value function on the machine’s own state space with optimal policy ω(m) = π*(ψ(m)). Such machines are optimal in the same sense as machines whose states are correctly-updated beliefs. Second, consistency is not correctness: whether a consistent interpretation exists depends only on the machine being interpreted, not on any property of its environment. An agent may hold a wrong model — its conclusions will then be wrong while its reasoning stays consistent — and its actions need only be optimal according to its own model, possibly suboptimal in the true environment. The authors flag this as a clear point of difference from the original Free Energy Principle literature, where the model is derived from the actual environment’s dynamics and so cannot differ from it. The hidden states and the rewards need not have any physical realisation at all; they exist only within the interpretation, and the machine never observes the rewards. Appendix C establishes that machines meeting Def. 5 exist by constructing one from the known optimal solution to Sondik’s POMDP.

The authors are careful about scope. The commitments are adopted because they permit precision, not because they are claimed to be realistic or the only reasonable choices; POMDPs are not the only possible formalisation of having a goal; they do not argue that all agents are rational or possess beliefs and goals. The framework requires exact Bayesian updating, so approximate inference — which the FEP does accommodate — falls outside it. The conclusion is offered as one worked example of the kind of agent definition sought, not as a settled general answer.

Key Ideas

Agency as consistent interpretation, not predictive advantage: ask whether the physical dynamics are consistent with an ascription of beliefs and goals, rather than whether the intentional stance out-predicts the physical stance.
An agent is a pair: a system together with an interpretation of it as a POMDP solution — agency is not an intrinsic property of the system alone.
Three conceptual commitments: systems are stochastic Moore machines; beliefs are Bayes-updated probability distributions; goals and rationality are supplied by POMDPs (expected discounted reward, optimal policy).
Interpretation map ψ : M → PH: sends internal machine states to beliefs over an interpretation-internal hidden state space; extended here with an action function α and a model kernel κ (the “influenced filtering” of Def. 3).
Definition 5: a stochastic Moore machine solves a POMDP when it has a consistent Bayesian influenced filtering interpretation and ω(m) = π*(ψ(m)) — it outputs the optimal policy’s action for the belief its state parameterises.
Parameterisation, not identity: machine states need only parameterise beliefs; ψ may be non-injective, so interpretation carries an automatic notion of coarse-graining of the internal state.
Proposition 1: for subjectively possible inputs, ψ(m) updates exactly per the Bayesian belief-state update; hence V*(ψ(m)) is an optimal value function on the machine’s state space — these machines are optimal in the same sense as belief-state machines.
Consistency ≠ correctness: existence of an interpretation depends only on the machine, not the environment. An agent can have a wrong model and act optimally only relative to it — a deliberate contrast with the FEP, where the model derives from actual environment dynamics.
Hidden states and rewards are interpretation-only: they need exist only mathematically, not physically; the machine never observes rewards. Even an output-less machine can have “actions” confined to the interpretation.
Existence is demonstrated, not assumed: Appendix C builds a qualifying stochastic Moore machine from the known optimal solution to Sondik’s POMDP.
Stated limits: exact Bayesian updating only (approximate inference excluded); POMDPs are not the only formalisation of goals; the commitments are chosen for precision rather than realism.

Connections

Conceptual Contribution

Value of Information

(page does not exist)

Finite-State Controller

(page does not exist)

Plan Graph

(page does not exist)

Witness Algorithm

(page does not exist)

Piecewise-Linear Convex Value Function

(page does not exist)

Policy Tree

(page does not exist)

Value Iteration

(page does not exist)

Bellman Equation

(page does not exist)

Markov Decision Process

(page does not exist)

Bayesian Filtering

(page does not exist)

Sufficient Statistic

(page does not exist)

Belief State

(page does not exist)

POMDP

(page does not exist)

The Knowledge Level

Reference: Allen Newell (1982). “The Knowledge Level.” Artificial Intelligence 18(1): 87-127. (AAAI Presidential Address, Stanford, 19 Aug 1980; also in AI Magazine 2(2), 1981.) URL

Summary

Newell’s AAAI-80 presidential address proposes that above the symbol level (data structures manipulated by programs) there exists a distinct knowledge level whose medium is knowledge and whose laws are rationality. At the knowledge level an agent is characterised by what it knows and what goals it has; its behaviour is predicted by the principle of rationality — “if an agent knows that one of its actions will lead to a goal, it will select that action” — without commitment to any particular representation or processing mechanism.

The paper motivates the proposal by diagnosing three tensions in early-1980s AI: the mystification of “representation,” the residue of the 1960s-70s theorem-proving controversy (Planner/Microplanner/Conniver’s “uniform procedures will not work” reaction against resolution), and the diversity of answers in the SIGART Special Issue on Knowledge Representation (Brachman and Smith’s survey showing no consensus on quantification, quotation, self-description, or evaluation). Newell’s resolution: treat knowledge as a competence-level notion analogous to physicists’ treatment of temperature — a level with its own laws, reduced to but not replaced by the symbol level. Representations are then understood as symbol-level implementations of knowledge, and we gain a principled way to talk about what an AI system knows without confusing it with how that knowledge is stored.

The Knowledge Level is foundational for agent-oriented programming (Shoham’s “mental state” framing), for the BDI tradition, for KQML’s and FIPA’s claim that ACL semantics should be defined at the level of beliefs/intentions rather than byte-strings, and indirectly for McCarthy’s Elephant 2000, whose speech-act semantics presupposes that one can talk coherently about what a program knows and is committed to, independently of implementation.

Key Ideas

Computer systems are describable at multiple levels (device, circuit, logic, register-transfer, program/symbol); the knowledge level sits above the symbol level.
Medium of the knowledge level: knowledge (distinct from the data structures that represent it).
Law of behaviour at the knowledge level: the principle of rationality — actions selected to achieve goals given what is known.
The knowledge level is a competence-level account: it predicts behaviour without specifying mechanism, analogously to economic rationality.
Representation is the symbol-level realisation of knowledge; mystifying representation conflates the levels.
Diagnostic of the theorem-proving backlash: “uniform procedures will not work” was a symbol-level reaction to a knowledge-level question.

Connections

Agent-Oriented Programming — Shoham explicitly situates AOP at the knowledge level; mental states are Newell-level predicates over agents.
Elephant 2000 - A Programming Language Based on Speech Acts — Elephant commits to knowledge-level program variables (propositions, commitments, past speech acts), making knowledge-level description the native semantics of programs.
Ascribing Mental Qualities to Machines — McCarthy’s ascriptivism is the philosophical cousin of Newell’s levels argument.
Knowledge Representation
Agent Communication Languages — ACL semantics in the KQML/FIPA tradition are knowledge-level (beliefs/intentions) rather than symbol-level (bit patterns).
KIF — intended as a lingua franca at the symbol level that preserves knowledge-level content across heterogeneous systems.
Common Sense Reasoning

Conceptual Contribution

Claim: AI systems have a level of description above the symbol level — the knowledge level — whose medium is knowledge and whose law is rationality; this level is reducible to but not replaceable by the symbol level, and recognising it clarifies decades of representation debates.
Mechanism: Levels-of-description methodology imported from computer architecture; principle of rationality as the behaviour law; knowledge characterised competence-theoretically (what follows from what an agent knows and wants, not how); representations reconceived as symbol-level implementations of knowledge-level content; diagnostic application to the theorem-proving controversy and the SIGART Special Issue.
Concepts introduced/used: Knowledge Level, Symbol Level, Principle of Rationality, Competence vs Performance, Knowledge Representation, Levels of Description.
Stance: foundational
Relates to: The conceptual ground for agent-oriented and BDI programming; provides the “what an agent knows” vocabulary that KQML, Agent Communication Languages, and Elephant 2000 - A Programming Language Based on Speech Acts rely on; complements McCarthy’s ascriptivist argument in Ascribing Mental Qualities to Machines.

Hidden Markov Model

(page does not exist)

Policy Iteration

(page does not exist)

Markov Processes

Stochastic processes with the memoryless property: future states depend only on the current state; Chomsky’s finite-state grammars are Markov sources, which he argued were inadequate for natural language.

In this vault

Three Models for the Description of Language

Planning and acting in partially observable stochastic domains

Summary

Key Ideas

Connections

Conceptual Contribution

Tags

Backlinks