Planning and acting in partially observable stochastic domains
1. Paper overview
In one sentence: A probability distribution over hidden states makes principled planning possible, but exact contingent policies can be costly to compute and may require substantial memory. e02e04e05e07e11e14e15e17
| At a glance | What to know |
|---|---|
| Research problem | Source description An agent must choose useful actions despite stochastic transitions and ambiguous observations. Acting only on the latest observation or most likely state can discard decision-relevant uncertainty. The paper asks how to plan from a complete, correct world model while valuing both an action’s immediate reward and the information it provides for subsequent choices. e02e03e04 |
| Core mechanism | Source description Connects operations-research POMDP theory to AI planning, treating sensing and world-changing actions within one reward objective. e02 |
| A key reported result | Tiger: one remaining decision under uniform uncertainty: LISTEN: −1 (analytically computed) Expected immediate reward. Analytical two-state example; b=(0.5,0.5), undiscounted horizon 1; no dataset or test split. Opening either door: −45, from equal probabilities of −100 and +10. Listening is preferable even without a future decision: here its role is avoiding a costly guess, not exploiting later information. e11e12 |
| Reading caution | Author claim Witness is not polynomial solely in the original POMDP size: its bound includes potentially large intermediate Q-vector sets. The authors cite prior evidence of impracticality when both states and observations exceed 15; this is a historical empirical warning, not a universal complexity cutoff. They also describe incremental pruning as empirically faster. e07e08e10e17 |
Core contributions
- Source description
Connects operations-research POMDP theory to AI planning, treating sensing and world-changing actions within one reward objective. e02
Figure 2. Belief estimation connects observation history to action selection. Original paper, p. 8 ↗
Excerpt from the authors’ paper; cropped without altering the figure or table.
How to read it. Start with the observation arrow entering SE, the state estimator. The arrow labeled b carries a probability distribution over the possible world states into the policy, π. Follow the policy’s outgoing action both to the world and around the lower feedback path into SE; the other feedback path returns the previous belief. These inputs match the Bayesian update in Section 3.3: predict the next-state distribution using the executed action, weight it by the new observation likelihood, and normalize. The policy then acts on this updated uncertainty. The diagram describes execution after offline planning; it contains no model-learning or neural-network training pipeline. e02e03e04
What it supports. The controller can respond differently to the same observation when earlier actions and observations imply different beliefs. Its information state is sufficient for planning under the specified model, allowing sensing and world-changing effects to enter the same future-reward calculation.
Where the evidence stops. The sufficiency and optimality argument assumes correctly computed beliefs and a correct supplied transition/observation model. This functional decomposition supplies no evidence for a learned One Model or Two Models classification.
2. Motivation
2.1 The problem and the proposed response
An agent must choose useful actions despite stochastic transitions and ambiguous observations. Acting only on the latest observation or most likely state can discard decision-relevant uncertainty. The paper asks how to plan from a complete, correct world model while valuing both an action’s immediate reward and the information it provides for subsequent choices. e02e03e04
2.2 What this reading follows
An agent can be uncertain about its location even when it knows how its world works. This paper shows how to turn that uncertainty into a state on which a policy can act. Its central progression is from Bayesian belief updates, to vector representations of contingent plans, to a search for the vectors that actually matter. The tiger example then makes the abstract machinery visible: a cheap listening action can delay an expensive mistake, and poorer observations demand more memory. Read the figures as explanations of a known-model planning method and worked solutions. The article’s broader performance comparisons refer to other work and do not supply a benchmark table. e02e04e05e07e11e14e15e17
3. Research context
We place the paper in the collection through its world–action interface. The catalog labels and the reading’s assessment are shown separately.
| Catalog dimension | Recorded classification |
|---|---|
| Major category | Foundational work |
| Architecture | Not applicable |
| Prediction paradigm | Not applicable |
| Quadrant | Not applicable |
3.1 Evidence-based assessment
Supports the recorded classification
The recorded foundational Theory & planning placement is supported. This is a known-model decision framework and exact planner, with model acquisition outside scope. Figure 2’s estimator/policy decomposition does not establish a learned One Model or Two Models architecture, and neither joint future/action prediction nor inverse dynamics describes the mechanism. The recorded architecture, prediction paradigm and quadrant remain Not applicable. e02e03e07
This is the collection’s architectural analysis, not a new related-work survey. Benchmark comparisons and their protocols appear in Section 6.
4. Problem formulation
4.1 Inputs and outputs
| Inputs | Outputs |
|---|---|
|
|
4.2 Equations and their role
5. Method in detail
5.1 Separate uncertainty about the state from uncertainty about the model
The POMDP begins with known transition, reward and observation functions. What is hidden during execution is the current state. The belief update first propagates the old distribution through the action’s transition probabilities, then uses the likelihood of the received observation to reweight possible resulting states. This ordering matters because the paper defines observations conditional on the resulting state and the action. The normalized distribution becomes the input to the policy. Offline planning evaluates actions by immediate expected reward plus observation-conditioned continuation value; online execution supplies the actual observation that selects a continuation. The learning problem is left outside the paper. Thus the framework explains why sensing can improve a decision without claiming that the agent learned an accurate model from data. e02e03e04e07
Figure 5. A continuous belief space can have a finite vector representation. Original paper, p. 12 ↗
Excerpt from the authors’ paper; cropped without altering the figure or table.
How to read it. The horizontal coordinate is b(s₁), the probability of the first state in a two-state world; the other probability is determined by normalization. Each line V_p represents the expected discounted return of one fixed t-step policy tree as the starting belief varies. Follow the thick upper boundary: a different tree supplies the maximum in each interval. The tree itself already contains observation-conditioned future choices, so a line is more than the value of a single immediate action. Section 4.1 expresses each line as b·α_p, with one component of α_p for each physical state. Section 4.2 then removes vectors that cannot improve this boundary. e05e06e10
What it supports. Finite-horizon optimal values are piecewise-linear and convex because they maximize finitely many linear tree values. This geometry makes exact representation possible without discretizing the belief axis. The first action comes from the maximizing tree, while later actions depend on the observations it anticipates.
Where the evidence stops. This is a schematic value diagram, with no numerical return scale. Convexity alone does not imply that every lower-entropy belief is more valuable. Infinite-horizon values can also require infinitely many facets.
5.2 Find the useful contingent plans without constructing all of them
A t-step tree specifies both what to do now and what to do after every possible observation. Exhaustive backup combines each root action with all lists of useful previous-horizon subtrees, so observation branching can generate a large intermediate set. Witness changes the order of work. For a fixed root action, it starts with an incomplete set of useful trees and searches for a belief at which that set underestimates the exact backup. A single-subtree replacement is the test candidate; a positive LP advantage identifies such a belief. The next accepted tree is optimized for that belief across every observation branch. After completing each action-specific Q-function, the algorithm pools and prunes the vectors. This is exact finite-horizon planning, but its cost still depends on potentially large intermediate representations. e05e06e07e08
Figure 9. One changed continuation can expose a missing useful policy. Original paper, p. 18 ↗
Excerpt from the authors’ paper; cropped without altering the figure or table.
How to read it. Read the root a(p) as fixed: this search operates inside the Q-function for one action. The outer triangles retain their observation-specific continuations, while the middle p′ replaces one subtree with another from the preceding horizon. The picture shows a candidate, not an automatically accepted improvement. Equation (1) asks whether there is a belief where this candidate exceeds every tree already retained. Algorithm 3 maximizes its minimum advantage δ subject to the belief simplex constraints. Only δ greater than zero supplies a witness. At that belief, the algorithm optimizes all observation branches to construct the best new tree, then searches further replacements. e05e06e07e08e09
What it supports. The witness theorem makes a local change in tree structure useful for a global completeness test over beliefs. Combined with a linear program, it avoids generating the complete observation-branch cross product before learning whether a candidate can improve the action-specific envelope.
Where the evidence stops. Appendix A’s observation-selection inequality omits O weights present in the main recursion and subsequent proof expansions. Treat that printed mismatch as requiring reconciliation. The diagram and Eq. (1) do not resolve it, and the stated complexity still depends on intermediate Q-set size.
5.3 Understand controller memory as retained decision-relevant history
The tiger diagrams show why policy compression depends on the problem and the starting belief. With one step remaining, a uniform belief makes opening unattractive even though listening cannot improve a later decision. With two steps, the depicted optimal policy listens first everywhere but needs different continuations in different belief regions. For the illustrated discounted solution, repeated policy structure can be folded into a loop, and a uniform start permits further trimming. Reader interpretation: the remaining node pointer is a compressed record of the history needed to choose actions under that model and objective. Reducing sensing reliability expands this record because more evidence must accumulate before opening. This interpretation is conditional: the missing numerical discount factor and precision-sensitive convergence preclude treating the shown graph as a universal controller. e11e12e13e14e15
5.4 Training and inference
During training
There is no learned representation, training dataset, loss function, frozen module or model-fitting stage. Offline computation is value iteration using supplied probabilities and rewards; learning the world model is explicitly left for future work. Exact finite-horizon backups can provide arbitrarily close discounted infinite-horizon approximations, without guaranteeing a finite exact representation in every problem. e02e07e10
During inference
During ordinary execution, update b after the actual action and observation, then select the root action of the best tree for the appropriate remaining horizon. A compatible plan graph instead uses the initial belief to select a node; thereafter it executes that node’s action and follows the observed edge. Graph compilation moves some online belief computation into controller memory. e04e05e14
5.5 Implementation flow
- Represent uncertainty explicitly
A belief b assigns probability to every enumerated state. The estimator SE receives the previous belief, executed action and new observation; the policy receives the updated distribution. This preserves distinctions between histories that look identical now but imply different states. e03e04
- Plan in belief space
The belief distribution is a sufficient statistic, so control becomes a fully observable MDP over a continuous belief space. Reward is an expectation over physical states. Correctness depends on the observation and transition models used by the estimator. e04
- Represent contingent futures by vectors
Each policy tree chooses a root action and an observation-specific continuation. Its alpha vector contains expected returns from each physical state. The maximum of their belief-weighted values is piecewise-linear and convex for finite horizons; pruning removes vectors that never improve that envelope. e05e06
- Search for missing useful trees
For each action, witness maintains a pointwise underestimate of that action’s exact Q-function. A linear program tests whether a single-subtree replacement beats every retained tree at some belief. At such a witness, the algorithm constructs the best tree by optimizing all observation branches, adds it, and continues until no witness remains. It then unions and prunes the action-specific sets. e07e08
6. Experiments & results
This foundational planning paper converts uncertainty about a hidden state into a probability distribution, solves for reward-maximizing behavior over that belief space, and sometimes compiles the solution into a finite-memory controller. Its witness algorithm constructs exact finite-horizon value functions without enumerating every observation-contingent tree. The tiger examples explain information gathering and controller memory; scalability and dependence on a correct supplied model remain central limits.
This theoretical and expository article contains original method diagrams and worked tiger policy graphs, but no quantitative benchmark table or empirical component-ablation study. Figures 17–18 provide a sensing-reliability diagnostic in place of such an ablation; Figure 12 supplies a numerical belief-region worked solution. Section 4.5 and Section 7 refer performance comparisons to other publications without providing their timing tables, protocols or uncertainty here. The edition therefore retains six original figures and supplies neither a fabricated table nor a claim of measured deployment performance. e10e12e14e15e17
6.1 Read the original evidence
Figure 12. Identical first actions can conceal different contingent plans. Original paper, p. 23 ↗
Excerpt from the authors’ paper; cropped without altering the figure or table.
How to read it. Read downward from two steps remaining to one. The five top intervals are expressed in b(s_l), the probability that the tiger is behind the left door, and their printed endpoints are rounded. Every top node selects LISTEN, but its continuation need not be the same. In the interval labeled [0.02, 0.39], TR leads to opening the left door, while TL leads to listening again. The middle interval routes either observation to LISTEN; the two extreme intervals open a door after either observation. Bottom intervals show the final-step decision map. These arcs agree with Bayesian updating and the asymmetric cost of opening the tiger’s door. e04e11e12
What it supports. The depicted two-step optimum needs five useful trees although all share a listening root. At uniform belief with one step left, the source computes −1 for listening versus −45 for opening. The graph therefore explains both information-dependent continuation and the value of avoiding a risky final guess.
Where the evidence stops. This is an undiscounted worked example, not an empirical success-rate table. Rounded interval boundaries should not become exact implementation thresholds. The displayed listen-first policy also does not establish uniqueness wherever actions tie.
Figure 17. The uniform-start policy can be executed with a node pointer. Original paper, p. 26 ↗
Excerpt from the authors’ paper; cropped without altering the figure or table.
How to read it. Begin at the central LISTEN node for the uniform initial belief. A TL observation moves rightward to another LISTEN node; a second TL reaches RIGHT, opening the door opposite the tiger’s inferred location. A TR observation instead returns the controller toward the center. The left side mirrors this logic. After opening either door, the TL/TR reset arc returns to the central node because the tiger is relocated uniformly. Section 5.4 obtains this graph by folding matching successive policy layers and deleting nodes unreachable from the uniform start. Once initialized, execution follows observations without explicitly recomputing a belief vector at every step. e11e13e14
What it supports. The five visible nodes encode three listening conditions and two door actions. In the source’s description, the agent listens until one side has been heard twice more than the other. The graph stores the relevant balance of evidence rather than a complete observation history.
Where the evidence stops. Trimming relies on the specified uniform initial belief and reset. The discounted example’s numerical γ is not supplied, and footnote 9 warns about precision-dependent convergence. This finite controller is an example, not a guarantee for arbitrary POMDPs.
6.2 Results and evaluation conditions
| Task & protocol | Reported result | Comparison & interpretation |
|---|---|---|
| Tiger: one remaining decision under uniform uncertainty Analytical two-state example; b=(0.5,0.5), undiscounted horizon 1; no dataset or test split. | LISTEN: −1 (analytically computed) Expected immediate reward | Opening either door: −45, from equal probabilities of −100 and +10. Listening is preferable even without a future decision: here its role is avoiding a costly guess, not exploiting later information. e11e12 |
| Tiger: two-step contingent policy Same rewards and transition/reset model; listening reliability 0.85; undiscounted horizon 2 over all beliefs. | Five listen-rooted policy trees with different continuations. Structure of the depicted optimal policy | The horizon-1 map has three action regions: LEFT, LISTEN and RIGHT. A common first action does not imply a single linear value segment. Observations can lead to different last-step actions; the figure is a worked solution, not a sampled success-rate evaluation. e11e12 |
| Tiger: memory required under noisier sensing Illustrated stationary discounted policies; uniform initial belief and reset; listening reliability changes from 0.85 to 0.65. Numerical discount factor unspecified. | 5 at reliability 0.65 (source-described controller rule). Net excess of observations on one side before opening the opposite door | 2 at reliability 0.85 in the trimmed controller. Less informative observations require a longer evidence history in these solutions. This comparison establishes controller structure, not a measured return gain or a universal threshold law. e11e13e14e15 |
6.3 Ablations and diagnostic examples
Read component removals and qualitative examples within their stated evaluation conditions.
Figure 18. Less reliable listening expands the illustrated controller’s memory. Original paper, p. 27 ↗
Excerpt from the authors’ paper; cropped without altering the figure or table.
How to read it. Compare this graph with Figure 17 while keeping the action labels and observation meanings fixed. Listening now identifies the correct side with probability 0.65 instead of 0.85. Start at the central node and follow TL along the right-hand chain toward RIGHT; intervening TR observations move back toward uncertainty. The left-hand chain behaves symmetrically. The extra LISTEN nodes retain finer distinctions in the accumulated observation history before committing to a door. Both door actions still return to the central node. Counting the graphic gives nine listening nodes plus two door nodes, compared with three plus two in the uniform-start 0.85 controller. e11e13e14e15
What it supports. The source describes a net observation margin of five before opening, compared with two for the more reliable sensor. This parameter change supplies a concrete diagnostic of the relationship between observation quality and controller memory, even though the physical tiger problem still has only two hidden states.
Where the evidence stops. This is a structural sensing-reliability diagnostic, not a benchmark ablation with returns, repeated runs or uncertainty bars. Unspecified discounting limits exact reproduction. The illustrated thresholds should not be treated as universal functions of sensor accuracy.
7. Analysis & limitations
7.1 What the evidence leaves open
Witness is not polynomial solely in the original POMDP size: its bound includes potentially large intermediate Q-vector sets. The authors cite prior evidence of impracticality when both states and observations exceed 15; this is a historical empirical warning, not a universal complexity cutoff. They also describe incremental pruning as empirically faster. e07e08e10e17
Infinite-horizon value functions can have infinitely many facets, and some optimal policies need more than finite-state memory. In the tiger computation, stable structure from horizons 56–105 and numerical equality at 105 must be read with the explicit precision-sensitivity caveat, not as a general finite-convergence guarantee. e10e13e16
The printed Appendix A observation-selection inequality omits O factors that appear in the main policy-tree recursion and subsequent proof expansions. This appears to be a derivation/typographic gap to reconcile; it is not evidence that the witness theorem is false. e05e09
The supplied article contains worked policy graphs and theoretical analysis, but no benchmark results table, timing protocol or statistical uncertainty for its cited performance claims. It does not evaluate model-learning error or physical robot execution. e02e10e11e17
7.2 Questions for discussion
- Which belief distinctions change the best continuation, and which can be merged into one controller node?
- How should numerical tolerances be chosen so that near-equal value vectors do not create misleading claims of exact convergence?
- How would a misspecified observation model affect the value assigned to listening?
8. Reproducibility audit
8.1 Requirements and known gaps
Reconstruct the two-state tiger model exactly, including the uniform reset after either door and uninformative post-opening observations. Use undiscounted finite horizons first. Implement Bayesian updates, alpha-vector backups, pruning and the witness LP with explicit tie handling. e04e06e08e11e12
For the discounted controller figures, the numerical discount factor, solver implementation and equality tolerances remain unspecified. Footnote 9 makes precision a material variable. Record these choices and compare value functions and actions, not just graph appearance; matching an assumed configuration would not recover the original experiment settings. e08e13e14
8.2 Proposed reproduction checks
The following checks are proposals motivated by the paper. They have not been run as part of this reading.
Check 1: Cross-check witness against exhaustive finite-horizon backups
Reader-proposed check, not run: implement two independent backups for the specified tiger model, one using exhaustive generation and pruning and one using witness LPs. Use undiscounted horizons one through four, identical rewards/reset probabilities and explicit tie handling. Compare their upper envelopes at every breakpoint of the combined two-state vector sets, not only at a sampled belief grid; also compare optimal action sets. Track candidate counts and LP calls separately from runtime. Repeat with tighter numerical tolerances. A persistent envelope discrepancy would falsify implementation equivalence; a different tied root action alone would not. Audit observation-likelihood weights against the p. 11 recursion when implementing the Appendix A argument. e05e06e07e08e09e11e12
Check 2: Test whether compiled memory preserves belief-policy decisions
Reader-proposed check, not run: for listening reliabilities 0.85 and 0.65, compare a compiled plan graph with explicit Bayesian belief tracking under the same rewards, uniform resets and observation streams. Sweep declared discount factors and equality tolerances because the source does not provide its numerical settings. Record action disagreements, expected discounted return, reachable node count and the net observation margin before opening. Include the unchanged 0.85 graph at reliability 0.65 as a control for insufficient memory. Agreement between the compiled and belief policies would support correct compilation for that configuration; systematic disagreement or different thresholds would challenge the implementation or parameter match, not automatically the paper’s theorem. e04e11e13e14e15
8.3 Reading coverage
Visual audit: Visually inspected the title/author page and every body/appendix page through PDF p. 33, including all Figures 1–18, Algorithms 1–3, the tiger parameter description, convergence footnote and Appendix A proof. All six final original crops were inspected individually. Figure 2 feedback paths, Figure 9 subtree replacement and LP sign, and Figures 12, 17 and 18 observation-arrow directions were checked against the text and equations. The Appendix A observation-weight mismatch is disclosed. References on pp. 34–36 were read in the complete text chunks; no separate supplement or code was inspected. The PDF contains no results table; performance comparisons cited to other works were not independently verified.
PDF pages inspected for this edition: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33. Appendix coverage: reviewed.
Original figures and tables remain the work of the source’s authors. Extractions preserve their scientific content; any HTML wrapper layout is disclosed with each figure. The surrounding reading notes are our own.
Text reading scope & known omissions
- Abstract and opening navigation example
- 1. Introduction
- 2. Markov decision processes: 2.1–2.3
- 3. Partial observability: 3.1–3.4
- 4. Value functions for POMDPs: 4.1–4.6, including 4.4.1–4.4.4 and Algorithms 1–3
- 5. Understanding policies: 5.1–5.4
- 6. Related work: 6.1–6.7
- 7. Extensions and conclusions
- Appendix A: Theorem A.1 and complete proof
- References [1]–[69]
Outside the original text pass
- Text extraction does not reconstruct figure images; inspect the retained PDF for figures and equation/table layout.
- Separate supplemental material availability has not been fully verified.
- Recovered-edition limitation: Author-hosted journal-formatted PDF linked from Leslie Pack Kaelbling's official MIT publications page. Header identifies Artificial Intelligence 101 (1998), pages 99–134, and all three catalog authors; all 36 pages retained. Publisher-hosted bytes were not available for comparison.
- Identity/version: the inspected title page matches the catalog title, all three authors and PII. This is the supplied author-hosted-publication-copy, versionDate 1998, with a revised-receipt date of 17 January 1998. No title or author discrepancy was observed; equality with publisher-hosted bytes is unverified.
- All nine supplied text chunks, covering all 36 PDF pages, were read. The extraction limitation was addressed by visually inspecting PDF pages 1–33, all 18 figures and Algorithms 1–3; reference pages 34–36 were read as text only.
- No separate supplement was supplied. Code was not inspected and no planning experiment was reproduced.
The visual audit above records the subsequent illustrated pass.
8.4 Traceable evidence
e01PDF p. 1 (journal p. 99), title, author affiliations, received/revised dates and PII
The observed title and all three authors match the catalog. The title page identifies Artificial Intelligence 101 (1998), 99–134, PII S0004-3702(98)00023-X, received 11 October 1995 and revised 17 January 1998; the affiliations are Brown University, Duke University and MCC.
Go to primary source ↓e02PDF pp. 2–3 (journal pp. 100–101), Section 1; p. 32, Section 7, final paragraph
The paper assumes a complete, correct dynamics model and reward structure, combines information gathering with world-changing actions, introduces an exact offline algorithm, and explicitly leaves acquisition of a world model outside its scope.
Go to primary source ↓e03PDF pp. 3–4, Sections 2.1–2.2; pp. 7–8, Sections 3.1–3.2 and Figure 2
Finite states and actions, transition probabilities T, expected immediate rewards R, observations Omega and observation probabilities O define the model. O conditions on the action and resulting state. The controller separates belief-state estimation from a policy acting on that belief.
Go to primary source ↓e04PDF pp. 8–10 (journal pp. 106–108), Sections 3.2–3.4, Bayesian update and belief-MDP reward equations
A properly computed probability distribution over states is sufficient for history and the initial belief. The update multiplies the transition prediction by the observation likelihood and normalizes. Expected belief reward is the belief-weighted sum of state rewards.
Go to primary source ↓e05PDF pp. 11–14 (journal pp. 109–112), Section 4.1, policy-tree recursion and Figures 4–7
An action node branches on observations. A policy tree has one state-value component per state; its belief value is a dot product. Maximizing over trees produces the piecewise-linear convex finite-horizon value function, whose maximizing tree determines the first action.
Go to primary source ↓e06PDF pp. 14–15 (journal pp. 112–113), Sections 4.2–4.3 and Figure 8
Vectors dominated by the upper envelope can be pruned, including vectors dominated collectively rather than by one vector alone. Exhaustive enumeration constructs |A||V_(t-1)|^|Omega| candidate trees before pruning.
Go to primary source ↓e07PDF pp. 16–17 (journal pp. 114–115), Section 4.4, Q-backup equation, Algorithm 2 and Section 4.4.1
Witness builds a parsimonious Q-function separately for each root action, then unions and prunes the sets. An incomplete set underestimates Q. At a witness belief, each observation branch receives the best previous-horizon subtree. Intermediate Q sets can be much larger than the final value representation.
Go to primary source ↓e08PDF pp. 17–19 (journal pp. 115–117), Sections 4.4.2–4.4.4, Figure 9, Eq. (1) and Algorithm 3
Replacing one subtree creates a candidate. The LP maximizes a lower bound delta on its advantage over every retained tree, with nonnegative belief components summing to one. Positive delta identifies a witness. The agenda explores single-subtree variants; the complexity bound includes intermediate action-specific sets and model precision.
Go to primary source ↓e09PDF pp. 32–33 (journal pp. 130–131), Appendix A, Theorem A.1 and proof; p. 11, policy-tree recursion
Appendix A states the single-subtree witness theorem. In the proof on p. 33, the displayed inequality selecting observation o* contains transition weights but no observation-likelihood factors, whereas the following value expansions and the p. 11 recursion contain O. This is a visible mismatch in the printed derivation.
Go to primary source ↓e10PDF pp. 20–21 (journal pp. 118–119), Sections 4.5–4.6
The authors describe incremental pruning as empirically faster than witness, citing other work. The infinite-horizon discounted value function remains convex but may have infinitely many facets; sufficiently long finite-horizon functions approximate it arbitrarily closely.
Go to primary source ↓e11PDF p. 21 (journal p. 119), Section 5.1, tiger rewards, transition and observation models
The tiger example has two states, three actions and two observations. Rewards are +10 for the safe door, -100 for the tiger door and -1 for listening. Listening preserves state with correct observation probability 0.85. Opening resets the state uniformly and yields either observation with probability 0.5.
Go to primary source ↓e12PDF pp. 21–23 (journal pp. 119–121), Section 5.2 and Figures 10–12
Finite-horizon tiger policies are undiscounted. At uniform belief with one step left, opening has expected reward -45 and listening -1. The depicted two-step policy has five listen-rooted trees and observation-conditioned continuations. Printed belief intervals use b(s_l); t is steps remaining.
Go to primary source ↓e13PDF pp. 23–25 (journal pp. 121–123), Section 5.3, Figure 14 and footnote 9
The discounted tiger graph structure first appears at t=56 and persists through t=105, when numerical comparisons no longer distinguish successive vectors. The text mentions differences beyond the fifteenth decimal place and warns that convergence is sensitive to precision. No numerical discount factor is supplied for these illustrated policies.
Go to primary source ↓e14PDF pp. 25–26 (journal pp. 123–124), Section 5.4 and Figures 15–17
Matching successive policy structures can be folded into a stationary plan graph. Starting at uniform tiger belief permits removal of unreachable nodes. Figure 17 has three listen nodes and two door nodes and implements a net observation difference of two. Execution maintains a node pointer and follows observation-labeled arcs.
Go to primary source ↓e15PDF p. 27 (journal p. 125), Figure 18, caption and Section 5.4 continuation
Reducing listening reliability from 0.85 to 0.65 produces the larger displayed graph and requires hearing the tiger five times more on one side than the other. The figure contains nine listen nodes and two door nodes. The text warns there is no known a priori bound on optimal graph size in terms of problem size.
Go to primary source ↓e16PDF pp. 27–31 (journal pp. 125–129), Sections 6.1–6.7
The related-work discussion compares imperfect knowledge, initial uncertainty, transitions, observations, objectives, representation and plan structure. Factored descriptions can be exponentially more compact than flat state models. Some infinite-horizon POMDPs require more than finite-state plans.
Go to primary source ↓e17PDF p. 32 (journal p. 130), Section 7
The authors cite prior experiments suggesting witness becomes impractical when both state and observation sets exceed 15, and motivate approximation on frequently visited beliefs. They refer to an 89-state, 16-observation hallway solution in other work without supplying a benchmark table here. World-model learning is future work.
Go to primary source ↓8.5 Primary sources
Planning and acting in partially observable stochastic domains ↗
PDF · 16,500 extracted words
Source fingerprint
71a6d1aee278e93c5fae8dd7d0c452c8b7b035af55d9dce2bc367d473bfc9645