Approximate Value Functions and Online Planning

Why exact methods stop scaling

The number of states can explode when several variables are combined: inventory by location, machine conditions, demand states, crews and time all multiply the state space.

Even if every state has only a handful of actions, storing or updating a value for every state can become impossible. Continuous variables make direct enumeration impossible altogether. Approximate methods replace an exact table with a function or restrict computation to the region relevant to the current decision.

Approximation introduces error, so the design question changes from “is the algorithm exact?” to “is the decision robust to the approximation?” Evaluate action quality, not only prediction error of the value function.

Value-function approximation

A compact function estimates the value of states or state-action pairs from features.

Simple approximations can be linear combinations of engineered features; more flexible approximators can represent nonlinear relationships. Features should capture operational drivers such as backlog, age, utilisation, risk state or remaining capacity. If critical information is absent from the features, no learning algorithm can recover it.

Approximation can generalise across similar states, reducing data and storage requirements. But errors can propagate through bootstrapping, and extrapolation into unseen regions can be unreliable. Maintain coverage diagnostics and conservative controls for safety-critical or high-cost states.

Receding-horizon planning

A practical online strategy plans only a limited number of steps ahead, executes the first action and replans after observing the new state.

This approach focuses computation on the immediate future and automatically incorporates new information. It is widely useful when long-horizon optimisation is too expensive but near-term dynamics dominate. A terminal value approximation can estimate consequences beyond the explicit horizon so the planner does not behave myopically near the horizon boundary.

Rollout policies

A rollout evaluates candidate first actions by simulating future trajectories under a baseline policy.

The method can improve a simple policy without solving the full dynamic program. For each candidate action, simulate the immediate transition and then follow the baseline policy for the remainder of the horizon. Average the simulated return. The best candidate becomes the chosen action.

Rollout quality depends on the baseline policy and simulation model. A strong baseline reduces variance and provides reasonable behaviour in branches that are not deeply searched. A poor model can produce confident but misleading action values.

Tree search, branch-and-bound and sparse sampling

Online planning can explicitly expand future action and outcome trees.

A full tree grows exponentially with depth. Branch-and-bound uses upper and lower bounds to discard branches that cannot beat the current best. Sparse sampling samples a limited number of next states rather than enumerating the entire transition distribution, making computational cost less dependent on the raw number of possible states.

Heuristics determine which nodes receive attention. Good heuristics combine domain knowledge with admissible or calibrated value estimates. The search should preserve enough exploration that an initially weak-looking branch is not discarded before important long-term benefit becomes visible.

Monte Carlo tree search

MCTS grows a search tree selectively using repeated simulated trajectories.

MCTS is attractive when a generative simulator is available even if transition probabilities are difficult to enumerate. Its performance depends on available computation, branching factor, rollout quality and exploration settings. For business use, constrain infeasible actions and embed hard safety or compliance rules outside the stochastic search when necessary.

Open-loop planning

Open-loop plans choose an action sequence without conditioning future actions on intermediate observations.

This greatly reduces branching because the planner does not need a separate branch for every observation. It can be appropriate when observations are limited, the planning horizon is short or replanning will happen frequently. It is less suitable when future information should strongly change the action.

A useful compromise is to optimise an open-loop sequence, execute the first action and re-optimise each period. This gains some feedback through replanning without constructing a full closed-loop tree.

Worked example: capacity allocation

A generic service operation allocates limited crews among preventive work, backlog reduction and urgent response while demand is uncertain.

The exact state includes too many combinations of jobs and crew locations. An approximate value function can summarise the long-term cost of backlog, while online search evaluates the next few assignment decisions. Rollouts under the current dispatch rule provide a baseline, and a limited tree search explores alternatives that may reduce future bottlenecks.

Management should compare the improved policy with the existing rule across simulated demand scenarios, including peaks and disruptions. The gain must exceed the implementation complexity and computation delay.

Approximation governance

Approximate planning requires explicit controls.

Application checklist

• Identify why exact dynamic programming is infeasible before introducing approximation.
• Choose state features that preserve decision-relevant information.
• Use terminal value estimates to reduce finite-horizon myopia.
• Validate rollout baselines and simulation models.
• Allocate search using bounds, sampling or MCTS rather than full enumeration.
• Use open-loop plans only when feedback loss is acceptable.
• Define computation limits, hard constraints and a fallback policy.
• Evaluate action performance across difficult scenarios, not just average value-fit error.