Monte-Carlo Planning in Large POMDPs
1. Paper overview
In one sentence: POMCP shares simulator trajectories between history-tree planning and particle-belief updates, gaining scalability while relying on finite samples and a supplied generative model. e02e03e05e06e08e19
| At a glance | What to know |
|---|---|
| Research problem | Source description Exact POMDP planning faces both a large belief distribution and exponentially many possible histories. The target is online action selection when explicit transition and observation probabilities are inconvenient, but a state-based simulator can sample their consequences. POMCP samples hidden starting states and future histories rather than enumerating either space. e02e03 |
| Core mechanism | |
| A key reported result | Rocksample (15,15): POMCP: 15.32 ± 0.28 Mean discounted return. 7,372,800 states; unfactored Monte-Carlo representation, prior rollout knowledge and one second per action. Evaluation uses up to 1,000 runs or 12 hours total. Rollout: 7.56 ± 0.25; full-width results are N/A. This establishes useful performance at the larger supplied benchmark, not numerical superiority over unrun full-width solvers or a proof of optimality. e09e11e12 |
| Reading caution |
Core contributions
Figure 1. Real feedback selects both a surviving search subtree and the particles for the next belief. Original paper, p. 4 ↗
Excerpt from the authors’ paper; cropped without altering the figure or table.
How to read it. Read the three drawings from left to right. In the first, action edges alternate with observation edges; N records visits, V records value estimates, and the S annotations display sampled state sets. Dashed continuations end in rollout rewards. The middle drawing follows the real action a2 and real observation o2. The right drawing keeps that compatible branch and relabels its root hao. The arrows agree with the rerooting procedure in Section 3.3. Use Algorithm 1 for the actual incremental-mean backup and final action selection: the displayed toy values should not be treated as an exact numerical execution trace. e04e05e06e07
What it supports. The useful connection is between control and inference. Choosing a branch after real feedback preserves previously simulated continuations, while the states accumulated at that history supply the next belief. The planner can reuse both forms of work instead of reconstructing a belief tree from explicit probabilities.
Where the evidence stops. The root shows V=1.5, although its displayed action-child counts and values imply a visit-weighted mean of 1: (3 × -1 + 6 × 2)/9. A V=-3 continuation also ends at r=+3. These schematic inconsistencies remain visible; use Algorithm 1 for the actual backup rule.
2. Motivation
2.1 The problem and the proposed response
Exact POMDP planning faces both a large belief distribution and exponentially many possible histories. The target is online action selection when explicit transition and observation probabilities are inconvenient, but a state-based simulator can sample their consequences. POMCP samples hidden starting states and future histories rather than enumerating either space. e02e03
2.2 What this reading follows
An agent in a partially observable world must choose an action without knowing which hidden state it occupies. POMCP handles this by sampling plausible states, exploring possible action–observation histories, and averaging simulated returns. The same trajectories also populate the particle beliefs used after real feedback arrives. This reading follows the original tree diagram into the benchmark evidence, asking when search adds value beyond rollouts and what domain knowledge changes. The central distinction is between the exact-belief convergence argument and the practical particle-based algorithm. The source studies simulated decision-making; its large state counts do not establish performance with learned dynamics or physical execution. e02e03e05e06e08e19
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-and-planning placement is supported. Architecture, prediction paradigm and quadrant are appropriately not applicable: POMCP combines a supplied simulator, history-tree control and particle inference, rather than a learned world/action architecture, joint future/action predictor or inverse-dynamics action extractor. e03e04e06e08
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 Simulate hidden states, but choose actions from histories
Begin with the distinction between a state and the information available to the agent. The simulator needs a concrete state to generate a successor, observation and reward. The real agent instead has a sequence of past actions and observations. PO–UCT therefore indexes its decision tree by histories while sampling a possible hidden state at the root of each simulation. Within that simulated trajectory, an action is chosen from history-based tree statistics or the history-based rollout policy. The observation produced by the simulator determines which continuation is visited. Several different sampled states may reach the same history and contribute returns to its estimate. This is how a state-based simulator can support planning over informational contingencies without constructing an explicit transition model over all beliefs. e03e04e06
Algorithm 1. The pseudocode shows where a simulated trajectory contributes both belief particles and action-value estimates. Original paper, p. 5 ↗
Excerpt from the authors’ paper; cropped without altering the figure or table.
How to read it. Start with Search at upper left: it samples a state from the initial distribution I or the current particle belief B(h), calls Simulate, and repeats until Timeout. Follow Simulate on the right. The discount cutoff returns zero; encountering a history outside the tree initializes its action children and switches to Rollout. Otherwise, the UCB expression chooses an action and G samples the successor state, observation and reward. The recursive call follows history hao and supplies the remaining discounted return. Read the four updates beneath it together: store the state, increment history and action counts, then update the action value. Finally, contrast Search’s return with Simulate’s selection: the real action uses V without the exploration bonus. e03e04e05e06e14e18
What it supports. At an existing tree node, the same simulator call supports two estimates: the stored state contributes to the particle belief, and the backed-up return contributes to the action value. The algorithm therefore makes the sharing in Figure 1 explicit. The particle and value updates serve different purposes even though they use the same trajectory.
Where the evidence stops. This is pseudocode, not a complete executable specification. It leaves zero-count UCB arithmetic and empty-belief recovery implicit. Section 2.3 describes terminal-state stopping, but the displayed procedures print only a discount cutoff; that cutoff alone cannot terminate Battleship, whose discount factor is one.
5.2 Use each trajectory to estimate value and belief
A return estimate answers how promising an action is; a particle belief answers which hidden states remain plausible. POMCP obtains both from the same simulations. During search, each visited history accumulates the states that reached it, together with counts and return statistics. After the real action and observation, the matching history becomes the new root. Its particles provide the next starting-state distribution and its descendants preserve useful search work. Section 3.2 explains the sampling principle separately: generate successors and accept those whose observations match the real one. My interpretation is that this computational sharing is the paper's central practical contribution. It does not erase approximation error: particle deprivation is acknowledged, and the convergence proof assumes the true belief rather than proving arbitrary finite particle sets sufficient. e05e06e07e08
5.3 Separate tree search, domain knowledge and computation
The PO-rollout baseline already uses Monte-Carlo belief updates, divides simulations across legal actions, and chooses the highest average return without building a tree. Comparing it with POMCP tests selective, contingent search. Preferred knowledge changes both rollout actions and tree initialization; Battleship additionally excludes deduced impossible cells. Read those interventions separately from the tree-versus-rollout contrast. The domain differences are revealing: Battleship reports over 50 moves saved against random play and over 25 against random preferred actions, yet only a small improvement over PO-rollout. PocMan reports undiscounted returns of over 300 versus 230 with preferences, and 260 versus 130 without them. Its axis and prose agree despite the generic discounted-return caption. My interpretation is that search helps more in some decision structures than others; the comparisons do not isolate the cause. Table 1’s full-width references also require separate accounting for offline preparation and factored-model access. e09e10e12e13e14e15e17
5.4 Training and inference
During training
No neural architecture, fitted dynamics loss or offline training stage is proposed. Counts and action values are estimated online from simulator returns. Experimental calibration sets c to the highest return in greedy POMCP sample runs minus the lowest sample-rollout return. e03e06e09
Preferred actions change two components: rollouts sample uniformly from the preferred set, and tree nodes receive optimistic values with initial count 10. Other actions receive the low reference value and count zero; the basic setting starts all values and counts at zero. e10
During inference
Search is repeated after each real observation. The experiments use a discount cutoff of 0.01, approximately 90 steps at gamma 0.95. Battleship and PocMan also add n/16 particles through domain-specific transformations when using n simulations. e06e09e14e16
5.5 Implementation flow
- Sample a hidden starting state
At the initial history, sample from I; later sample from the particle collection B(h). The simulator consumes this concrete state, but the search policy conditions on observable history. Different hidden states can therefore contribute to the same history node. e03e04e06
- Search histories and finish with rollouts
Within the tree, choose actions using a value estimate plus a UCB exploration bonus. Sample the next state, observation and reward through G. At a newly encountered history, expand the tree and continue with a history-based rollout policy. Back up discounted simulation returns as running means. e04e06
- Reuse simulations as belief samples
Each represented history stores particles encountered there. The standalone belief update accepts simulated successor states whose generated observation matches the real observation. POMCP shares these samples with tree search, avoiding an explicit full-state Bayes update. e05e06
- Act, observe and reroot
After the search budget expires, select the action with greatest estimated value, execute it in the environment, and receive the actual observation. Retain the subtree and particles for the resulting history hao; prune incompatible branches before the next search. e06e07
6. Experiments & results
POMCP plans under partial observability by sharing simulator trajectories between a history-based UCT search and an unweighted particle belief. It selects an action, observes the environment, and reuses the compatible subtree. The supplied simulator is not learned. Experiments show scalability in Rocksample, Battleship and PocMan, with domain-dependent gains from search and preferred actions; the formal guarantee assumes the true belief state.
The selected visuals cover the method diagram, complete pseudocode, quantitative table and Rocksample diagnostic comparisons. Figure 2’s lower Battleship and PocMan plots contain truncated terminal simulation-axis glyphs within the supplied PDF itself; inspecting the full page and wider crops does not recover them. Those panels are therefore not selected as standalone visuals. Page 8 remains inspected, and all four base-report results are retained, including the lower panels’ findings supported by readable axes, curves and domain-specific prose. No complete value is inferred for either obscured tick. The source also duplicates the Battleship preferred-rollout legend, leaves its five-ship fleet composition inconsistent with four listed sizes, and labels PocMan returns as undiscounted in the axis and prose despite the generic discounted caption. These discrepancies remain explicit. The diagnostic comparisons do not separately ablate reinvigoration or isolate preferred rollouts from optimistic initialization; the reproduction checks propose those investigations without claiming new results. e06e07e10e12e13e14e15e17
6.1 Read the original evidence
Table 1. The larger Rocksample result is useful at a fixed online budget, with important differences in comparator setup. Original paper, p. 7 ↗
Excerpt from the authors’ paper; cropped without altering the figure or table.
How to read it. Each column is a Rocksample (n,k) instance: n gives the grid side and k the number of rocks. Read the state-count row before comparing algorithm returns. The caption, inspected on the original page, assigns one second per action to online algorithms. POMCP and rollout use prior rollout knowledge and unfactored representations. Full-width online methods additionally use knowledge computed offline by PBVI, while SARSOP receives roughly 1,000 seconds offline; all full-width methods receive exactly factored models. Consequently, compare POMCP with rollout for the most direct Monte-Carlo contrast, and treat the full-width rows as differently configured reference points. e09e11e12
What it supports. On the 7,372,800-state instance, POMCP reports 15.32 ± 0.28 against rollout's 7.56 ± 0.25. On the smallest instance its 20.71 ± 0.21 remains below HSVI-BFS's 21.46 ± 0.22. The result supports scalable planning with the supplied simulator, rather than uniform dominance across methods.
Where the evidence stops. The paper does not identify the ± terms as standard deviations, standard errors or confidence intervals. N/A entries are missing comparisons, not zero scores. Offline computation and factored-model access prevent reading the entire table as a matched-budget ranking.
6.2 Results and evaluation conditions
| Task & protocol | Reported result | Comparison & interpretation |
|---|---|---|
| Rocksample (11,11) 247,808 states; simulated benchmark, no learned train/test split. Monte-Carlo methods use prior rollout knowledge and one second per action; full-width methods receive factored models. | POMCP: 20.01 ± 0.23 Mean discounted return | Rollout: 8.70 ± 0.29; SARSOP: 21.56 ± 0.11 with approximately 1,000 seconds of offline computation. POMCP substantially improves over rollout at the table budget. SARSOP is an offline comparison with different information and computation; the reported ± terms are not defined as a particular uncertainty statistic. e09e11e12 |
| Rocksample (15,15) 7,372,800 states; unfactored Monte-Carlo representation, prior rollout knowledge and one second per action. Evaluation uses up to 1,000 runs or 12 hours total. | POMCP: 15.32 ± 0.28 Mean discounted return | Rollout: 7.56 ± 0.25; full-width results are N/A. This establishes useful performance at the larger supplied benchmark, not numerical superiority over unrun full-width solvers or a proof of optimality. e09e11e12 |
| Battleship 10 × 10 simulated board, approximately 10^18 states, binary hit observations and gamma = 1; Figure 2 varies simulations and preferred-action knowledge. | Authors report more than 50 moves saved versus random play and more than 25 versus random preferred actions. Mean moves saved relative to simple play | POMCP provides only a small benefit over PO-rollout; the authors attribute this to small action-value differences and high return variance. These are source-reported aggregate comparisons, not exact digitized endpoints or a human-subject comparison. e09e14e15 |
| PocMan Partially observable simulated 17 × 19 maze, four ghosts and ten observation bits; planning discount is 0.95. Figure 2 sweeps simulation budgets. | With preferred actions: over 300; basic POMCP: 260. Mean undiscounted return | Corresponding PO-rollout values: 230 and 130, respectively, as summarized in the text. The panel axis and domain-specific prose report undiscounted scores despite the generic discounted-return caption. These values summarize the high-budget regime, not every point in the sweep. e09e16e17 |
6.3 Ablations and diagnostic examples
Read component removals and qualitative examples within their stated evaluation conditions.
Figure 2, upper Rocksample panels. Search budget and preferred actions have distinct visible effects on Rocksample performance. Original paper, p. 8 ↗
Excerpt from the authors’ paper; cropped without altering the figure or table.
How to read it. Start with the lower logarithmic axis, which measures simulations. The upper time axis is calibrated only for POMCP with preferred actions, so it is not a universal time conversion for every curve. Red denotes basic behavior and green denotes preferred behavior. Solid curves show the planner; dotted curves show PO-rollout. The source legend calls the planner POMC, while the surrounding paper calls it POMCP. Compare solid and dotted curves within the same color to inspect the added tree-search benefit. Compare colors within one method to inspect the combined knowledge intervention. The blue SARSOP reference appears only in the smaller-instance panel. e09e10e11e13
What it supports. Both panels show preferred POMCP improving substantially as its simulation budget grows and outperforming preferred rollouts over the larger budgets shown. The comparison therefore supports a benefit from selective tree search beyond simply running the same style of rollout policy more often. The bigger instance remains harder at the displayed budgets.
Where the evidence stops. Preferred actions alter both rollout sampling and initial tree values/counts; these plots do not isolate either component. The caption allows 1,000 runs or a 12-hour limit per point and does not define the error bars. The time axes apply only to preferred POMCP.
7. Analysis & limitations
7.1 What the evidence leaves open
The convergence argument assumes the true current belief and finite horizon. It does not establish optimality for a fixed particle budget. Section 3.2 explicitly warns of particle deprivation; rejection-based updates also make rare observations a potential sampling bottleneck. e05e08
Preferred-action comparisons combine rollout changes with node initialization; Battleship additionally excludes deduced impossible cells from search. The experiments do not isolate these effects or separately ablate reinvigoration. e10e14e13e15e17
Experiments use supplied simulators, not learned model errors or physical deployment. Exact per-condition run counts, uncertainty definitions, hardware and software versions are not reported. Battleship specifies five ships but enumerates only four sizes, leaving the fleet composition unresolved. e09e12e14e18
7.2 Questions for discussion
- When does tree search improve decisions beyond the same simulator budget spent on rollouts?
- How much of the preferred-action gain comes from rollout quality versus optimistic tree initialization?
- How quickly does an approximate belief fail after unlikely observations, and can reinvigoration recover it?
8. Reproducibility audit
8.1 Requirements and known gaps
Reproduction requires a resettable simulator, initial-state sampler, legal actions, reward/observation rules, exploration calibration and the stated preference heuristics. Fix random seeds and disclose the initial particle budget. Rocksample details rely partly on the cited benchmark definition rather than a self-contained specification. e03e09e11e18
Implement and document terminal handling, zero-count exploration and empty-belief recovery: the pseudocode is not a complete executable specification. In particular, its discount cutoff cannot terminate undiscounted Battleship by itself. Domain transformations and their observation-consistency tests need explicit implementation choices. e06e14e16e18
Reader-proposed checks should separate preferred rollouts from optimistic initialization and compare particle beliefs against exact Bayes updates on a small enumerable instance. Measure both return and belief accuracy while matching simulator budgets; neither check was run here. e05e09e10
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: Factor the preferred-action intervention
Reader-proposed, not executed: on Rocksample (11,11), run a two-by-two comparison crossing uniform versus preferred rollouts with zero versus source-style optimistic initialization. Keep the simulator, initial beliefs, simulation budgets and calibration of c fixed, use paired episode seeds, and include PO-rollout controls for each rollout policy. Record mean discounted return, uncertainty with a stated definition, simulator calls and wall-clock time. If optimistic initialization adds little once rollouts are preferred, the published combined gain should be attributed primarily to rollout quality; if only their combination helps, the effects interact. A tree-search advantage should persist against its corresponding rollout control, not merely against the weakest basic condition. e09e10e11e13
Check 2: Test belief accuracy independently of search quality
Reader-proposed, not executed: use a small enumerable Rocksample instance with documented benchmark semantics and compute exact Bayes beliefs as an oracle. Replay the same action–observation histories through the source's rejection-based particle update at several particle counts, with and without a declared observation-consistent reinvigoration rule. Include histories containing low-probability observations. Measure total-variation distance from the oracle, distinct particle states, rejected simulator calls and empty-belief frequency. Then plan from each belief with the same search budget and compare action choices and return. Persistent belief error despite larger budgets, or improved belief accuracy without improved decisions, would distinguish a filtering failure from a search limitation. The reinvigoration rule for this diagnostic would be an explicitly new experimental choice. e03e05e06e08e09e11
8.3 Reading coverage
Visual audit: All three supplied text chunks and all nine PDF pages were read. Page 1 verified title, authors and affiliations; pages 2–3 established notation, simulator and search background; pages 4–5 verified Figure 1, particle updates, Algorithm 1 and action/observation arrows; pages 5–6 covered proof assumptions and experiment configuration; pages 7–8 covered every table cell, all four Figure 2 panels, task details and discussion; page 9 contained references. The four selected final crops were extracted and visually inspected: Figure 1, complete Algorithm 1, Table 1 and the two upper Figure 2 panels. They retain their original labels, equations, axes and legends. Long captions are excluded from crops; their conditions were read on the declared full pages and incorporated into the explanations. Both former lower-panel crops were also inspected against page 8: their terminal simulation-axis glyphs are clipped inside the original graphics, so neither is selected as a final visual. Their supported numerical results and methodological details remain in the base report and walkthrough, with pages 6–8 supplied for verification. Figure 1 has inconsistent illustrative values; Algorithm 1 supplies the verified backup rule. Rocksample legends say POMC; Battleship duplicates a legend entry; PocMan’s axis and prose conflict with the generic caption. No graphics or glyphs were reconstructed. No appendix is present; separate supplements and linked code were not inspected.
PDF pages inspected for this edition: 1, 2, 3, 4, 5, 6, 7, 8, 9. Appendix coverage: not present.
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 1 Introduction (pp. 1–2)
- 2 Background, including 2.1–2.4 (pp. 2–3)
- 3 Monte-Carlo Planning in POMDPs, including 3.1–3.3 and Algorithm 1 (pp. 3–5)
- 4 Convergence, both lemmas and Theorem 1 (pp. 5–6)
- 5 Experiments, all three domains (pp. 6–8)
- 6 Discussion (p. 8)
- References (p. 9)
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.
- Separate supplemental material availability has not been fully verified; no separate supplement was supplied.
- Text extraction did not reconstruct figure images; this gap was addressed by visually inspecting all nine PDF pages, both figures, Table 1 and Algorithm 1.
- No code was inspected and no experiments were reproduced.
- The title and both authors match the catalog. The supplied proceedings PDF prints no revision identifier or revision date; no equivalence to other editions is established.
- Figure 2 has source-clipped terminal simulation-axis glyphs in its Battleship and PocMan panels. Both panels were inspected, but they are excluded from the final crops; their supported results remain in this report.
The visual audit above records the subsequent illustrated pass.
8.4 Traceable evidence
e01PDF p. 1, title and author block
Observed title is Monte-Carlo Planning in Large POMDPs. Authors are David Silver (MIT, Cambridge, MA 02139) and Joel Veness (UNSW, Sydney, Australia). The supplied PDF has no printed revision identifier/date.
Go to primary source ↓e02PDF pp. 1–2, Abstract and Section 1
The paper motivates sampling hidden starting states and histories to address belief dimensionality and history growth; the same simulations support planning and belief updates.
Go to primary source ↓e03PDF p. 2, Sections 2.1–2.2
A history consists of actions and observations. The resettable generative simulator G samples successor state, observation and reward from a state and action; it replaces access to explicit transition and observation distributions.
Go to primary source ↓e04PDF p. 3, Sections 2.3–2.4 and 3.1; p. 4, Section 3.1 continuation
PO–UCT stores history visitation counts and return estimates, samples the initial state from the belief, selects tree actions by UCB, and continues beyond the tree with a history-based rollout. One new history node is added per simulation.
Go to primary source ↓e05PDF p. 4, Section 3.2, particle-belief equation and update paragraphs
The unweighted belief uses K particles and Kronecker deltas. Simulated successors matching the real observation are accepted. The text states convergence as particle count grows and warns of particle deprivation, motivating reinvigoration.
Go to primary source ↓e06PDF pp. 4–5, Section 3.3 and Algorithm 1
Nodes store count, value and particles. Search samples initial states; Simulate calls G, recurses, stores particles and updates counts and mean returns. Search returns the largest unaugmented root action value; real feedback selects the next root and incompatible branches are pruned.
Go to primary source ↓e07PDF p. 4, Figure 1 and caption; p. 5, Algorithm 1 and Section 3.3 continuation
The method graphic alternates action and observation branches, depicts execution of a2 followed by observation o2, and retains the corresponding subtree as hao. Particle sets are displayed with S labels. It illustrates a toy problem with no intermediate rewards. The displayed root is N=9, V=1.5; its action children show N=3, V=-1 and N=6, V=2. A displayed N=1, V=-3 continuation ends at a rollout reward labeled r=+3, another inconsistency in the illustrative values.
Go to primary source ↓e08PDF pp. 5–6, Section 4, Lemmas 1–2 and Theorem 1
Under a true belief and finite horizon, the history-derived MDP preserves value and rollout distribution. The paper transfers UCT convergence to PO–UCT for suitable c and states an O(log N(h)/N(h)) value-bias rate.
Go to primary source ↓e09PDF p. 6, Section 5, first three experimental-setup paragraphs
Evaluation runs each problem 1,000 times or for up to 12 hours. PO-rollout uses Monte-Carlo belief updates and allocates n/|A| rollouts per legal action. Exploration uses Rhi minus Rlo; the discount cutoff is 0.01. Battleship/PocMan add n/16 transformed particles for n simulations.
Go to primary source ↓e10PDF p. 6, Section 5, preferred-action setup paragraph
Preferred rollouts sample uniformly from Ap. Preferred actions initialize at Vinit = Rhi and Ninit = 10; others at Rlo and zero. The basic variant uses all legal actions and zero initial values/counts.
Go to primary source ↓e11PDF p. 6, Section 5, Rocksample paragraphs
Rocksample places k rocks in an n × n grid and asks the robot to collect valuable samples and exit east. POMCP evaluates (7,8), (11,11), and (15,15) without factoring; preferences use counts of valuable/unvaluable observations. The text separately claims a four-second online comparison to a 1,000-second offline solver.
Go to primary source ↓e12PDF p. 7, Table 1, all rows/columns and complete caption
State counts are 12,544, 247,808 and 7,372,800. POMCP reports 20.71 ± 0.21, 20.01 ± 0.23 and 15.32 ± 0.28; rollout reports 9.46 ± 0.27, 8.70 ± 0.29 and 7.56 ± 0.25. SARSOP reports 21.39 ± 0.01 and 21.56 ± 0.11 for the two smaller tasks. AEMS2 and HSVI-BFS report 21.37 ± 0.22 and 21.46 ± 0.22 on (7,8). Online algorithms receive one second per action; full-width online methods use offline PBVI knowledge, SARSOP uses about 1,000 seconds offline, and full-width models are exactly factored. The caption does not define the ± statistic.
Go to primary source ↓e13PDF p. 8, Figure 2, upper Rocksample (11,11) and (15,15) panels and caption
Both panels plot average discounted return against simulations. Solid tree-search curves and dotted rollout curves compare basic and preferred settings; the left panel includes SARSOP. Legends abbreviate the planner as POMC. The top time axis applies only to preferred POMCP; the caption specifies 1,000 runs or 12 hours per point.
Go to primary source ↓e14PDF p. 7, Section 5, Battleship paragraphs
Battleship has a 10 × 10 board, binary observations, -1 per shot, +100 terminal reward, gamma = 1 and about 10^18 states. The text says five ships but lists four sizes. Reinvigoration swaps or moves ships. Preferences exclude diagonal neighbors of hits. The authors report over 50/25 moves saved against random/random-preferred play and only a small tree-search benefit over PO-rollout.
Go to primary source ↓e15PDF p. 8, Figure 2, lower-left Battleship panel and caption
The average-return curves for tree search and rollouts remain close within a preference setting; preferences improve the low-budget regime. The source legend repeats PO-rollouts: preferred. The last x-axis tick glyph is clipped in the embedded source graphic; no extra condition is inferred from the duplicated label.
Go to primary source ↓e16PDF pp. 7–8, Section 5, PocMan environment and heuristic paragraphs
PocMan uses a 17 × 19 maze, four ghosts, power pills and gamma = 0.95. Ten observation bits encode sight, hearing, touch and smell, giving 1,024 observations; the paper estimates about 10^56 states and specifies four actions. Reinvigoration teleports one or two ghosts and accepts consistency with the last observation; preferences chase visible ghosts under power pills and otherwise avoid them and backtracking.
Go to primary source ↓e17PDF p. 8, Figure 2, lower-right PocMan panel, caption and PocMan results paragraph
The panel labels its y-axis Average Undiscounted Return; the prose likewise reports over 300 versus 230 with preferences and 260 versus 130 without them. The generic caption instead says discounted return. The top time axis belongs only to preferred POMCP. A terminal x-axis tick glyph is clipped in the embedded source graphic. The text links source code and a demonstration; their availability was not verified.
Go to primary source ↓e18PDF p. 3, Section 2.3; p. 5, Algorithm 1; pp. 6–8, Section 5
Rollouts are described as terminating at a terminal state or discount horizon, but Algorithm 1 explicitly prints only the discount cutoff. The pseudocode does not specify zero-count UCB arithmetic or empty-belief recovery. The experiment section does not report hardware/software versions, seeds, a numerical initial particle count, uncertainty definitions, or exact completed run counts for time-limited conditions.
Go to primary source ↓e19PDF p. 8, Section 6 Discussion
The authors argue that best-first sampling and shared belief updates make planning practical in large, unfactored problems; the presented demonstrations use Rocksample, Battleship and PocMan simulators.
Go to primary source ↓8.5 Primary sources
Monte-Carlo Planning in Large POMDPs ↗
PDF · 5,702 extracted words
Source fingerprint
fa4c2e0d4a42c82b22bf4163a0096a95ea0cffa000ce81dc33e0aa97146fc92f