Planning and Monte Carlo Tree Search

Computing at Decision Time

A learned policy compresses past optimization into parameters:

a_t\sim\pi_\theta(\cdot\mid s_t).

Most computation happens during training, so acting may require only one forward pass. Planning takes the opposite bargain. Given a model, it spends computation on the current decision:

\boxed{ a_t =\operatorname{PLAN} \left(s_t,\widehat p,\widehat r,\text{budget}\right) }.

The model may be exact game rules, a conventional simulator, or a learned dynamics model. A planner only needs to query consequences such as

s'\sim\widehat p(\cdot\mid s,a).

Dynamic programming attempts to solve the MDP globally:

V^*(s) =\max_a \left[ r(s,a) +\gamma\sum_{s'}p(s'\mid s,a)V^*(s') \right], \qquad \forall s\in\mathcal S.

A planner can instead approximate only the decision rooted at the current state:

a_t\approx\arg\max_a Q^*(s_t,a).

It ignores states unreachable from $s_t$ and branches that do not matter to the present action. This gives the basic tradeoff:

\boxed{ \begin{aligned} \text{learning:}&\quad \text{compute now so later decisions are cheap},\\ \text{planning:}&\quad \text{compute later to improve the current decision}. \end{aligned} }.

Strong systems combine them. A policy proposes promising actions, a value function estimates distant consequences, and local search improves the final recommendation.

An open-loop plan fixes an entire action sequence

A=(a_1,\ldots,a_H)

before any future state is observed. Conditioned on $A$ ,

p(s_{1:H+1}\mid A) =p(s_1) \prod_{t=1}^{H} p(s_{t+1}\mid s_t,a_t).

A closed-loop policy reacts to each realized state:

p_\pi(s_{1:H+1},a_{1:H}) =p(s_1) \prod_{t=1}^{H} \pi(a_t\mid s_t) p(s_{t+1}\mid s_t,a_t).

Optimizing $H$ actions is simpler than optimizing a mapping from every possible future state to an action. The price is that a fixed sequence cannot react when reality differs from prediction.

Optimizing Action Sequences

For deterministic model dynamics

s_{t+1}=f(s_t,a_t),

an $H$ -step plan solves

\boxed{ A^* =\arg\max_{a_{1:H}} \sum_{t=1}^{H} \gamma^{t-1}r(s_t,a_t) \quad\text{s.t.}\quad s_{t+1}=f(s_t,a_t) }.

Once $s_1$ and $A$ are fixed, every predicted state is determined. The objective is therefore a function of the action sequence alone:

\begin{aligned} J(A;s_1) &=r(s_1,a_1) +\gamma r(f(s_1,a_1),a_2)\\ &\quad+\gamma^2 r(f(f(s_1,a_1),a_2),a_3) +\cdots. \end{aligned}

For stochastic dynamics, we maximize expected return:

\boxed{ A^* =\arg\max_A \mathbb E \left[ \sum_{t=1}^{H}\gamma^{t-1}r(s_t,a_t) \;\middle|\;s_1,A \right] }.

The integral over future states is usually intractable, so $B$ model rollouts estimate it:

\widehat J(A) =\frac1B\sum_{b=1}^{B} \sum_{t=1}^{H}\gamma^{t-1} r(s_t^{(b)},a_t),

s_{t+1}^{(b)} \sim\widehat p(\cdot\mid s_t^{(b)},a_t).

More particles reduce Monte Carlo noise but require more model calls.

Random shooting

Random shooting samples candidates from a proposal

A^{(1)},\ldots,A^{(N)}\sim q(A),

scores each through the model, and selects

A^*=\arg\max_{A^{(i)}}\widehat J(A^{(i)}).

Its model-step cost is approximately

O(NBH).

Candidates are independent, so evaluation parallelizes almost perfectly. But a near-optimal sample teaches the planner nothing about where to sample next.

Cross-entropy method

The cross-entropy method, or CEM, repeatedly moves its proposal toward high-return action sequences. At iteration $j$ ,

A^{(1)},\ldots,A^{(N)} \sim q_{\phi_j}(A).

Let $\mathcal E_j$ contain the top $M$ candidates. The next proposal solves

\boxed{ \phi_{j+1} =\arg\max_\phi \sum_{i\in\mathcal E_j} \log q_\phi(A^{(i)}) }.

This is maximum-likelihood fitting to the elite set.

See derivation

Define the empirical elite distribution

\widehat p_{\mathcal E}(A) =\frac1M\sum_{i\in\mathcal E} \delta(A-A^{(i)}).

We want $q_\phi$ to approach this distribution. Expanding the forward KL,

\begin{aligned} D_{\mathrm{KL}} (\widehat p_{\mathcal E}\|q_\phi) &=\mathbb E_{\widehat p_{\mathcal E}} \left[ \log\widehat p_{\mathcal E}(A) -\log q_\phi(A) \right]. \end{aligned}

The elite-distribution entropy is independent of

Therefore,

\arg\min_\phi D_{\mathrm{KL}} (\widehat p_{\mathcal E}\|q_\phi) =\arg\max_\phi \frac1M\sum_{i\in\mathcal E} \log q_\phi(A^{(i)}).

For continuous actions, let

q_\phi(A)=\mathcal N(A;\mu,\Sigma), \qquad A\in\mathbb R^{Hd_a}.

The Gaussian maximum-likelihood updates are

\mu_{\mathcal E} =\frac1M\sum_{i\in\mathcal E}A^{(i)},

\Sigma_{\mathcal E} =\frac1M\sum_{i\in\mathcal E} (A^{(i)}-\mu_{\mathcal E}) (A^{(i)}-\mu_{\mathcal E})^\top.

Practical implementations often use diagonal covariance and smooth the update:

\mu\leftarrow \alpha\mu_{\mathcal E} +(1-\alpha)\mu_{\text{old}},

with an analogous covariance update.

\textbf{Cross-Entropy Trajectory Optimization}

\begin{aligned} &\text{Initialize }q_{\phi_0}(a_{1:H}).\\[0.25em] &\text{For }j=0,\ldots,J-1:\\[0.25em] &\qquad \text{sample }N\text{ sequences from }q_{\phi_j},\\[0.25em] &\qquad \text{estimate each return with model rollouts},\\[0.25em] &\qquad \mathcal E_j\leftarrow\text{top }M\text{ sequences},\\[0.25em] &\qquad \phi_{j+1}\leftarrow \arg\max_\phi \sum_{i\in\mathcal E_j}\log q_\phi(A^{(i)}).\\[0.25em] &\text{Return the best sequence or the final proposal mean.} \end{aligned}

CEM is derivative free, parallel, and compatible with non-smooth rewards. Its search space still has dimension $Hd_a$ , so long horizons and high-dimensional actions require rapidly increasing computation.

Replanning Creates Feedback

Model-predictive control, or MPC, repeatedly solves the open-loop problem. At time $t$ ,

A_t^* =\arg\max_{a_{t:t+H-1}} \widehat J(a_{t:t+H-1};s_t).

It executes only the first action,

a_t=a_{t,t}^*,

observes the real next state, and replans:

A_{t+1}^* =\arg\max_{a_{t+1:t+H}} \widehat J(a_{t+1:t+H};s_{t+1}).

Each internal optimization is open loop, but their composition defines a state-dependent controller:

\boxed{ \pi_{\mathrm{MPC}}(s) =\operatorname{first} \left[ \arg\max_A\widehat J(A;s) \right] }.

MPC therefore recovers feedback without optimizing a complete policy inside each plan.

Replanning limits propagated error

Suppose the model predicts

\widehat s_{t+1}=f_\phi(s_t,a_t),

but the real transition produces

s_{t+1}=\widehat s_{t+1}+\epsilon_t.

Full open-loop execution continues from the incorrect prediction:

\widehat s_{t+2} =f_\phi(\widehat s_{t+1},a_{t+1}).

MPC resets the next plan at the observed state:

\widehat s_{t+2} =f_\phi(s_{t+1},a_{t+1}).

It does not remove model bias, but it prevents one incorrect predicted state from being propagated indefinitely.

Horizon is a three-way tradeoff

A longer horizon sees delayed consequences but increases optimization dimension, computation, and accumulated model error. A short horizon is reliable but myopic.

A terminal value compresses the tail:

\boxed{ J_H(A) =\sum_{k=0}^{H-1} \gamma^k r(s_{t+k},a_{t+k}) +\gamma^H\widehat V(s_{t+H}) }.

The planner handles the near future explicitly, while the value function amortizes everything beyond the search horizon.

With uncertain learned models, an ensemble can propagate particles through different plausible dynamics. A risk-sensitive score is

J_{\text{risk}}(A) =\mathbb E[J(A)] -\beta\sqrt{\operatorname{Var}[J(A)]}.

The mean rewards actions with high predicted return; the penalty rejects candidates whose quality depends on unsupported model behavior.

\textbf{CEM Model-Predictive Control}

\begin{aligned} &\text{At each real state }s_t:\\[0.25em] &\qquad \text{warm-start an action-sequence proposal},\\[0.25em] &\qquad \text{run CEM for a fixed compute budget},\\[0.25em] &\qquad \text{score candidates across stochastic or ensemble particles},\\[0.25em] &\qquad \text{execute only the first action of the best plan},\\[0.25em] &\qquad \text{observe }s_{t+1}\text{ and shift the proposal forward}. \end{aligned}

Forward Search

Trajectory optimization searches over complete action sequences. Forward search instead builds a tree rooted at the current state.

At a state node, the agent chooses an action. At the following chance node, the environment chooses a next state according to the transition distribution.

With $h$ decisions remaining, exact finite-depth expectimax obeys

\boxed{ Q_h(s,a) =r(s,a) +\gamma\sum_{s'}p(s'\mid s,a)V_{h-1}(s') },

\boxed{ V_h(s)=\max_a Q_h(s,a) }.

For deterministic dynamics, the chance-node expectation collapses:

Q_h(s,a) =r(s,a)+\gamma V_{h-1}(f(s,a)).

At the depth limit, we need a boundary condition. We can use no tail value,

V_0(s)=0,

a terminal outcome,

V_0(s)=z,

Monte Carlo rollouts,

V_0(s)\approx\frac1K\sum_{k=1}^{K}G^{(k)},

or a learned critic,

V_0(s)\approx v_\theta(s).

This is the same explicit-near-future plus learned-tail compromise used by MPC.

Given a rollout policy $\pi$ , simulate $K$ trajectories after each root action and estimate

\widehat Q^\pi(s_t,a) =\frac1K\sum_{k=1}^{K}G_t^{(k)}.

As the number of independent rollouts grows,

\widehat Q^\pi(s_t,a) \xrightarrow[K\to\infty]{P} q^\pi(s_t,a).

Choosing

\pi'(s_t)=\arg\max_a\widehat Q^\pi(s_t,a)

performs local one-step policy improvement over the rollout policy.

The obstacle is combinatorial growth. With $|\mathcal A|$ action branches, up to $|\mathcal S|$ chance outcomes, and depth $H$ , a full tree can require

O\!\left((|\mathcal A||\mathcal S|)^H\right)

nodes. Search must decide which branches deserve computation.

Monte Carlo Tree Search

Monte Carlo tree search, or MCTS, incrementally constructs a partial tree. Each simulation follows four phases:

\boxed{ \text{selection} \longrightarrow \text{expansion} \longrightarrow \text{evaluation} \longrightarrow \text{backup} }.

After each simulation, updated statistics change where the next simulation goes.

For every tree edge $(s,a)$ , store

N(s,a)=\text{visit count},

W(s,a)=\text{total backed-up return},

\boxed{ Q(s,a)=\frac{W(s,a)}{N(s,a)} }.

The state visit count is

N(s)=\sum_aN(s,a).

Selection and expansion

Starting at the root, a tree policy selects edges until it reaches a terminal state, a depth limit, or an unexpanded action. The model then generates a successor:

s'\sim\widehat p(\cdot\mid s,a).

Only that local part of the tree is expanded. MCTS does not enumerate every child at every depth before looking deeper.

Leaf evaluation

At the new leaf $s_L$ , estimate the remaining value with a rollout,

\widehat V(s_L) =\sum_{k=0}^{T-L-1}\gamma^k r_{L+k},

an average over several rollouts, or a value network:

\widehat V(s_L)=v_\theta(s_L).

Rollouts require more model steps and inherit the rollout policy's weakness. A value network is faster but adds approximation error.

Backup

Initialize

G_L=\widehat V(s_L).

Moving backward along the selected path,

G_t=r_t+\gamma G_{t+1},

then update

N(s_t,a_t)\leftarrow N(s_t,a_t)+1,

W(s_t,a_t)\leftarrow W(s_t,a_t)+G_t,

Q(s_t,a_t)\leftarrow \frac{W(s_t,a_t)}{N(s_t,a_t)}.

In a two-player zero-sum game, the player perspective alternates, so value changes sign at each level:

v_{\text{parent}}=-v_{\text{child}}.

The root decision

The planner can select the root action with the highest estimated value,

a_t=\arg\max_a Q(s_t,a),

or the greatest visit count,

\boxed{ a_t=\arg\max_a N(s_t,a) }.

Visit counts aggregate both estimated quality and the search algorithm's confidence, so they are often more stable than a noisy maximum of empirical means.

\textbf{Monte Carlo Tree Search}

\begin{aligned} &\text{Initialize a tree rooted at the current state }s_0.\\[0.25em] &\text{For }k=1,\ldots,K:\\[0.25em] &\qquad \textbf{select}\text{ edges with the tree policy},\\[0.25em] &\qquad \textbf{expand}\text{ one unvisited successor with the model},\\[0.25em] &\qquad \textbf{evaluate}\text{ the leaf by rollout or value function},\\[0.25em] &\qquad \textbf{back up}\text{ discounted returns along the path}.\\[0.25em] &\text{Choose the root action with the largest visit count.} \end{aligned}

MCTS is an anytime algorithm. One simulation gives a crude answer; every additional simulation can refine it; and the current recommendation is available whenever the compute budget expires.

Upper Confidence Trees

Selection must exploit actions with high empirical value while exploring actions with little evidence. UCT treats each state node as a multi-armed bandit and chooses

\boxed{ a =\arg\max_a \left[ Q(s,a) +c\sqrt{\frac{\log N(s)}{N(s,a)}} \right] }.

The first term exploits known value. The second is an uncertainty bonus.

Deriving the exploration bonus

Assume returns for action $a$ are independent and bounded in an interval of width $R$ . If $n_a=N(s,a)$ samples have empirical mean $\widehat\mu_a$ , Hoeffding's inequality gives

\Pr\!\left( \mu_a\ge\widehat\mu_a+\epsilon \right) \le \exp\!\left(-\frac{2n_a\epsilon^2}{R^2}\right).

Choosing failure probability $\delta=N(s)^{-\alpha}$ produces

\boxed{ \epsilon =R\sqrt{ \frac{\alpha\log N(s)}{2N(s,a)} } }.

See derivation

Set the concentration bound equal to the desired failure probability:

\exp\!\left(-\frac{2n_a\epsilon^2}{R^2}\right) =N(s)^{-\alpha}.

Taking logarithms,

-\frac{2n_a\epsilon^2}{R^2} =-\alpha\log N(s).

Solving for $\epsilon$ gives

\epsilon =R\sqrt{ \frac{\alpha\log N(s)}{2n_a} }.

Replacing $n_a$ with $N(s,a)$ yields the UCT exploration term.

The bonus is large when an action has few visits, shrinks as that edge is sampled, and grows slowly when the parent receives more visits. Unvisited actions are assigned infinite priority so every legal action is tried.

The coefficient $c$ sets the allocation strategy:

c\downarrow \Rightarrow\text{more exploitation}, \qquad c\uparrow \Rightarrow\text{more exploration}.

This is not ordinary online bandit exploration. Simulated rewards have no direct value; only the final real root action matters. UCT uses a bandit rule at the metalevel to decide which computation is most likely to improve that final choice.

Neural-Guided Search

Plain MCTS wastes simulations rediscovering which actions look plausible and estimating every leaf from scratch. A neural network can provide both answers:

f_\theta(s) =\left( p_\theta(\cdot\mid s), v_\theta(s) \right).

When a state is expanded, store the policy prior

P(s,a)=p_\theta(a\mid s),

and use

\widehat V(s)=v_\theta(s)

instead of a long random rollout. The policy focuses search; the value head shortens it.

PUCT

PUCT incorporates the learned prior into selection:

\boxed{ a =\arg\max_a \left[ Q(s,a) +c_{\mathrm{puct}}P(s,a) \frac{\sqrt{N(s)}}{1+N(s,a)} \right] }.

Each factor has a separate role:

Q(s,a)=\text{backed-up evidence},

P(s,a)=\text{network preference},

\sqrt{N(s)}=\text{pressure to revisit alternatives},

1+N(s,a)=\text{decay after an edge is explored}.

A wrong prior delays an action but does not permanently remove it. As the parent is revisited, search can accumulate enough evidence to overturn the network.

After $K$ simulations, visit counts define a search-improved policy:

\boxed{ \pi_{\mathrm{MCTS}}(a\mid s) =\frac{N(s,a)^{1/\tau}} {\sum_bN(s,b)^{1/\tau}} }.

At $\tau=1$ , this is the normalized visit distribution. As $\tau\to0$ , it concentrates on the most visited action. A higher temperature preserves diversity during early self-play.

Search as Policy Improvement

Neural-guided MCTS creates a stronger local policy than the raw network:

p_\theta(\cdot\mid s) \xrightarrow{\text{search}} \pi_{\mathrm{MCTS}}(\cdot\mid s).

The network can then learn to imitate search, amortizing that expensive computation into its next forward pass:

\pi_{\mathrm{MCTS}}(\cdot\mid s) \xrightarrow{\text{training}} p_{\theta'}(\cdot\mid s).

AlphaZero-style learning repeats these two operations through self-play.

At state $s_t$ , MCTS produces

\pi_t(a)=\pi_{\mathrm{MCTS}}(a\mid s_t).

The player samples or selects

a_t\sim\pi_t,

applies the exact game dynamics, and continues until outcome

z\in\{-1,0,+1\}.

For each visited state, store

(s_t,\pi_t,z_t),

where $z_t$ is expressed from the perspective of the player to move at $s_t$ .

The network minimizes

\boxed{ \mathcal L(\theta) =\mathbb E_{(s,\pi,z)} \left[ (z-v_\theta(s))^2 -\sum_a\pi(a\mid s) \log p_\theta(a\mid s) \right] +\lambda\|\theta\|_2^2 }.

The value loss fits expected outcomes:

v_\theta(s)\approx\mathbb E[z\mid s].

The policy cross-entropy fits the search distribution:

p_\theta(\cdot\mid s)\approx\pi_{\mathrm{MCTS}}(\cdot\mid s).

See derivation

The policy loss is

\mathcal L_\pi =-\sum_a\pi(a\mid s)\log p_\theta(a\mid s).

Meanwhile,

D_{\mathrm{KL}}(\pi\|p_\theta) =\sum_a\pi(a\mid s)\log\pi(a\mid s) -\sum_a\pi(a\mid s)\log p_\theta(a\mid s).

The target entropy

Therefore minimizing policy cross-entropy is equivalent to minimizing

D_{\mathrm{KL}}(\pi\|p_\theta).

\textbf{Self-Play with Neural MCTS}

\begin{aligned} &\text{Initialize policy-value network }f_\theta.\\[0.25em] &\text{Repeat:}\\[0.25em] &\qquad \text{generate games against the current network},\\[0.25em] &\qquad \text{at every state, run PUCT-guided MCTS},\\[0.25em] &\qquad \text{store }(s_t,\pi_{\mathrm{MCTS},t},z_t),\\[0.25em] &\qquad \text{fit the policy head to search visit counts},\\[0.25em] &\qquad \text{fit the value head to terminal outcomes}.\\[0.25em] &\text{Use the improved network to guide the next search.} \end{aligned}

The loop is

\boxed{ f_{\theta_k} \xrightarrow{\mathrm{MCTS}} \pi_k \xrightarrow{\mathrm{self\text{-}play}} \mathcal D_k \xrightarrow{\mathrm{training}} f_{\theta_{k+1}} }.

Search improves the network locally; training distills those improvements globally; the stronger network then makes the next search more efficient.

Self-play also creates a moving curriculum. The opponent improves with the learner, keeping states and outcomes informative without human move labels. This works especially well when the environment supplies exact rules, legal actions, terminal outcomes, and unlimited simulated experience.

When Planning Is Worth the Cost

Planning trades latency for decision quality. Approximate costs make the contrast concrete:

\begin{aligned} \text{policy:}&\quad O(\text{one network pass}),\\ \text{CEM:}&\quad O(NBHJ)\text{ model steps},\\ \text{MCTS:}&\quad O(KD)\text{ model steps}, \end{aligned}

where $J$ is the number of CEM iterations, $K$ the number of tree simulations, and $D$ their average depth.

Trajectory optimization and CEM are natural for continuous actions:

a_t\in\mathbb R^{d_a}.

MCTS is natural when actions are discrete, legal moves can be enumerated, and the branching factor is manageable. A continuous action space has infinitely many potential children, so ordinary visit-count search needs additional action sampling or progressive widening.

Planning is most attractive when individual decisions are valuable, model queries are cheap, computation is available between actions, and similar states do not recur often enough to justify solving everything in advance.

A learned policy is preferable when latency is strict or the same decision structure is repeated at massive scale. In practice, the strongest compromise is often

\boxed{ \text{learned policy and value} +\text{ limited online search} }.

The policy supplies breadth, the value function supplies depth, and planning spends the remaining budget only on branches relevant to the state in front of us.