PaperlayerView exact revision on arXiv

Source-linked AI summary

POLY-HOOT: Monte-Carlo Planning in Continuous Space MDPs with Non-Asymptotic Analysis

Weichao Mao, Kaiqing Zhang, Qiaomin Xie, Tamer Başar

arXiv:2006.04672v2cs.AIcs.LG

TL;DR

The paper addresses the limited theory for Monte-Carlo planning in continuous state-action spaces, where finite-space MCTS methods do not directly apply. It introduces POLY-HOOT, combining MCTS with HOO and a polynomial confidence bonus, and proves polynomial-rate convergence to an arbitrarily small neighborhood of the optimal value function.

  • Problem

    Monte-Carlo planning in continuous state-action spaces is less understood, while most existing MCTS solutions work primarily in finite spaces and face challenges from non-stationary rewards.

  • Method

    POLY-HOOT augments MCTS with HOO and replaces HOO’s logarithmic upper-confidence bonus with a polynomial bonus suited to non-stationary bandit rewards.

  • Results

    POLY-HOOT’s value estimate converges at a polynomial rate to an arbitrarily small neighborhood of the optimal value function, with experiments corroborating the theoretical findings.

  • Takeaways & Limitations

    The analysis supports using non-stationary bandits with polynomial bonuses for continuous-space MCTS and reports superior POLY-HOOT performance on the evaluated tasks.

  • Takeaways & Limitations

    The convergence analysis depends on smoothness, reward-convergence, concentration, and bounded-depth assumptions, while the proof must address strong non-stationarity and interdependent bandits.

Abstract

from arXiv · show

Monte-Carlo planning, as exemplified by Monte-Carlo Tree Search (MCTS), has demonstrated remarkable performance in applications with finite spaces. In this paper, we consider Monte-Carlo planning in an environment with continuous state-action spaces, a much less understood problem with important applications in control and robotics. We introduce POLY-HOOT, an algorithm that augments MCTS with a continuous armed bandit strategy named Hierarchical Optimistic Optimization (HOO) (Bubeck et al., 2011). Specifically, we enhance HOO by using an appropriate polynomial, rather than logarithmic, bonus term in the upper confidence bounds. Such a polynomial bonus is motivated by its empirical successes in AlphaGo Zero (Silver et al., 2017b), as well as its significant role in achieving theoretical guarantees of finite space MCTS (Shah et al., 2019). We investigate, for the first time, the regret of the enhanced HOO algorithm in non-stationary bandit problems. Using this result as a building block, we establish non-asymptotic convergence guarantees for POLY-HOOT: the value estimate converges to an arbitrarily small neighborhood of the optimal value function at a polynomial rate. We further provide experimental results that corroborate our theoretical findings.

1 Introduction

The paper targets Monte-Carlo planning in continuous state-action spaces, where existing methods face enormous branching factors and difficult non-stationary analysis. It introduces POLY-HOOT, combining MCTS with enhanced HOO and proving polynomial-rate convergence.

  • Motivation: Continuous state-action spaces remain difficult for MCTS because enormous branching factors make finite-space solutions generally incompatible with robotics and control applications.Manual discretization also requires a pre-specified resolution, creating a trade-off between fine coverage and sufficient exploitation.
  • Analytical challenge: MCTS analysis is complicated by non-stationary, interdependent state-action value estimates because lower-level search policies change across simulations.Earlier exponential concentration assumptions for UCB1-based analyses are described as unrealistic in general.
  • Approach: POLY-HOOT combines MCTS with HOO, which adaptively partitions continuous actions and identifies potentially optimal regions without manual discretization.The algorithm builds on prior empirical HOOT work but adds theoretical analysis and an enhanced HOO strategy.
  • Contributions: The paper enhances HOO with a polynomial bonus, analyzes its regret under non-stationary rewards, and proves that POLY-HOOT converges to an arbitrarily small neighborhood of the optimal value function at a polynomial rate.Experiments corroborate the theoretical findings and demonstrate superior performance for POLY-HOOT.
  • Related work: Prior continuous-space MCTS methods include HOOT, HOLOP, kernel regression, Voronoi partitioning, and progressive widening, but they lack the paper’s combination of bandit-guided exploration and theoretical guarantees.Most MCTS variants remain restricted to finite-action problems.

2 Preliminaries

The preliminaries formulate continuous-space discounted MDPs and explain MCTS and HOO as the two building blocks of POLY-HOOT. They emphasize deterministic transitions, stochastic bounded rewards, and hierarchical non-stationarity.

  • Markov Decision Processes: The MDP has continuous state and action spaces, deterministic transitions, bounded stochastic rewards, and discount factor γ, without requiring compact state-action domains.The planner accesses the MDP through a generative model that returns sampled next states and rewards for queried state-action pairs.
  • Monte-Carlo Tree Search: MCTS estimates a state’s value by repeatedly traversing a multi-step look-ahead tree, selecting actions through tree policies and querying a generative model.Each tree node represents a state, while each edge represents a state-action pair leading to a subsequent state.
  • Monte-Carlo Tree Search: MCTS bandit rewards are highly non-stationary because changing lower-level policies alter reward distributions, while hierarchical dependence makes analysis non-trivial.The paper follows Shah et al. (2019) by using polynomial bonuses to obtain concentration results under this non-stationarity.
  • Hierarchical Optimistic Optimization: HOO handles continuous arms by recursively bisecting the action domain and selecting paths toward leaves using upper-confidence B-values.Each node covers a subset of the action space, and the selected leaf corresponds to the arm that is pulled.

3 Algorithm: POLY-HOOT

POLY-HOOT replaces discrete action selection in MCTS with HOO agents and modifies HOO for non-stationary rewards. Its bounded-depth tree and polynomial bonus balance exploration with exploitation.

  • HOO-Based Action Selection: POLY-HOOT places a continuous-armed HOO agent at each MCTS node, using HOO_query for action selection and HOO_update to propagate realized rewards.This replaces the discrete UCB1 agent used in finite-action MCTS.
  • Polynomial Bonus: The algorithm replaces HOO’s logarithmic confidence bonus with a polynomial bonus because hierarchical MCTS rewards are non-stationary and logarithmic bonuses do not guarantee convergence.The paper notes that polynomial bonuses also appear in empirically successful AlphaGo Zero.
  • Bounded-Depth HOO Tree: POLY-HOOT limits the maximum depth of each HOO tree and repeats the action at maximum depth, stopping indefinitely fine action refinement.This bounded depth is intended to fully exploit explored actions when non-stationarity could otherwise leave search trapped in an early suboptimal region.
  • Bandit Setting: Each HOO agent models a continuous action set whose stochastic payoff represents the cost-to-go or Q-value of an action, with rewards converging toward a limiting mean-payoff function.The analysis assumes polynomial convergence of temporary mean-payoff functions and concentration conditions for observed rewards.
  • Bandit Setting: The HOO analysis assumes geometric shrinkage of covering-set diameters and local smoothness near globally optimal arms, weaker than global Lipschitz continuity.These assumptions support continuous-space action refinement while allowing less restrictive behavior away from optimal actions.

4 Main Results

The main results analyze enhanced HOO in non-stationary continuous-armed bandits and propagate its guarantees recursively through MCTS. Under stated smoothness, convergence, and concentration conditions, POLY-HOOT achieves polynomial-rate value convergence.

  • Proof Strategy: The proof recursively applies the enhanced-HOO result from the deepest MCTS level upward, transferring convergence and concentration properties to the root node.Intermediate-node rewards are generated by downstream bandits, producing the non-stationarity handled by the induction.
  • 4.1 Convergence of POLY-HOOT: POLY-HOOT’s value estimate converges to a γ^Dε_0 neighborhood of the optimal value function at rate O(n^-ζ), with ζ ∈ (0, 1/2).Choosing the MCTS depth D appropriately makes the neighborhood around the optimal value arbitrarily small.
  • Assumptions: The analysis requires reward convergence and concentration assumptions, including polynomial convergence of fixed-arm mean payoffs and concentration parameters for observed rewards.The theorem also imposes parameter constraints such as α > 3 and a bounded HOO depth satisfying ρ^H̄ < n^(η−1).
  • 4.2 Enhanced HOO in the Non-Stationary Setting: Enhanced HOO preserves the convergence and concentration rates of non-stationary bandit rewards when its parameter conditions and assumptions are satisfied.This theorem supplies the intermediate guarantee used to analyze every MCTS level.
  • Technical Challenges: The proof must handle interdependent non-stationary bandits, infinitely many candidate arms, and sufficient exploitation within a limited-depth HOO tree.The authors identify these as technical challenges in extending finite-space MCTS analysis to continuous domains.

5 Simulations

POLY-HOOT is evaluated on continuous-action control tasks against discretized UCT, PUCT, and HOOT, with results showing stronger performance on more difficult tasks and modest computational cost.

  • The evaluation uses CartPole, a harder-gravity CartPole-IG variant, Inverted Pendulum Swing-up, and LunarLander, with average rewards and standard deviations reported over 40 runs.
  • POLY-HOOT significantly outperforms HOOT on LunarLander, while HOOT and POLY-HOOT perform slightly better than the other methods on Pendulum.On CartPole, all four algorithms achieve optimal rewards; on CartPole-IG, discretized UCT and PUCT fail to achieve optimal performance.
  • On CartPole-IG, discretized UCT and PUCT underperform because uniform-grid or random actions are not smooth enough for the task's larger momentum.
  • LunarLander's high-dimensional action space makes fine-grained sampling difficult for discretized UCT and PUCT, while deeper search and sparse large rewards intensify non-stationarity.The authors attribute POLY-HOOT's advantage over HOOT to its polynomial bonus term handling this more severe non-stationarity.
  • POLY-HOOT requires slightly more computation than discretized UCT and PUCT but remains more time-efficient than HOOT when its maximum HOO-tree depth is limited.The computation-time comparison is reported for one decision on CartPole-IG, averaged over 10 runs.

6 Conclusions

The paper develops POLY-HOOT for continuous state-action MDPs by combining MCTS with an enhanced HOO strategy, and supports it with non-asymptotic theory and experiments.

  • POLY-HOOT augments MCTS with HOO using a polynomial bonus term, whose non-stationary regret analysis supports convergence guarantees and experimental corroboration.The paper argues that polynomial-bonus non-stationary bandits may guide future continuous-space planning algorithms for robotics and control.

Broader Impact

The paper addresses a theoretical gap in continuous-domain MCTS and connects its results to planning, reinforcement learning, multi-armed bandits, robotics, and control.

  • The work establishes a theoretical analysis of continuous-domain MCTS through the lens of non-stationary bandits, which had not previously been established.
  • The authors suggest that non-stationary bandit algorithms may guide new planning methods with better empirical performance and applications in continuous-domain robotics and control.
  • The paper reports no anticipated ethical issues or disadvantages because it is theory-oriented.

Supplementary Materials for “POLY-HOOT: Monte-Carlo Planning

The supplementary material describes POLY-HOOT's HOO routines and algorithm inputs, outputs, initialization, depth limit, and action-selection steps.

  • The HOO query and update routines provide the implementation details used by Algorithm 1.
  • At an unvisited state and MCTS depth, the algorithm initializes an HOO agent with a root tree and infinite initial bounds, then reuses the previously constructed agent on later visits.
  • During HOO traversal, the algorithm chooses an arm from a node's action set and associates that action with the selected node, while maximum depth prevents further exploration.
  • POLY-HOOT receives MCTS depth, state, and round information, and outputs the action to take using a maximum HOO depth parameter.

B Proof of Theorem 2

The proof establishes concentration and convergence bounds for enhanced HOO by decomposing the tree and regret into regions, then bounding each contribution.

  • Tree decomposition: The analysis partitions the HOO tree into T1, T2, T3, and leaf set L according to near-optimality and depth.T1 contains descendants of IH, T2 contains shallow near-optimal nodes, and T3 contains descendants of boundary nodes Jh.
  • Regret decomposition: Regret is decomposed according to the selected node, with separate terms for T1, T2, T3, and repeated-play leaves.The proof analyzes these components individually using concentration inequalities and near-optimality properties.
  • Region-wise bounds: Nodes in near-optimal regions contribute regret controlled by their distance from the optimum, while suboptimal boundary regions are bounded through node-count and tail estimates.The proof uses the inclusion of relevant node domains in Xε and bounds the number of near-optimal or boundary nodes.
  • Parameter choice: The concentration analysis chooses the depth parameter H so that the approximation term 4ν1ρHn decreases at the target polynomial rate.The proof sets ρH = n^λ and compares n^(λ+1) with the concentration scale n^η.
  • Conclusion: The resulting bounds show that the enhanced HOO regret decreases polynomially in n under the stated parameter conditions.The proof obtains a polynomially decreasing bound for the contribution from T3 and analogous bounds for the other regions.

B.5 Completing proof of concentration

The proof combines the concentration bounds for each regret component to obtain the desired overall concentration property.

  • Combining bounds: The component inequalities remain valid for 0 < z < 1 because their right-hand sides exceed the trivial probability upper bound of 1.For z ≥ 1, the individual bounds are combined directly.
  • Final concentration result: The combined concentration inequality has exponent controlled by a constant β′ > 1 that is independent of n and z.β′ depends on the proof parameters, including α, β, η, ξ, and the depth limitation.

B.6 Convergence results

The convergence proof bounds regret at the finite-depth leaves and propagates the resulting value-estimation guarantees upward through MCTS by induction.

  • Finite-depth regret: The proof treats the special case of one optimal node at depth ¯H; the multiple-optimal-node case is bounded by a constant multiple.Regret is separated into above-depth, near-optimal-leaf, and suboptimal-leaf contributions.
  • Value-iteration connection: The MCTS analysis views depth-D search as approximate value iteration and uses contraction of value iteration with respect to the L∞ norm.The empirical root reward is shown to approach the depth-D value-iteration result, which is then related to the optimal value function.
  • Induction step: At each level, reward sequences satisfy the convergence and concentration assumptions required by enhanced HOO, allowing the result to propagate recursively toward the root.The induction uses independent bounded rewards together with deterministic value estimates at successor states.
  • Inductive conclusion: The resulting propositions establish convergence and concentration properties for value estimates at successive MCTS depths, including the root.The induction identifies the relevant value function as the result of a finite number of value-iteration steps from the leaf oracle.

C.3 Completing proof of Theorem 1

The proof completes Theorem 1 by combining concentration bounds for optimal and suboptimal HOO nodes with tree-visit arguments, yielding a polynomial-probability convergence guarantee at the MCTS root.

  • Theorem 1 concludes that the root-node value estimate satisfies the stated convergence bound after n MCTS simulations, with polynomially decaying error terms.The proof transfers the result to the root through an inductive argument and the empirical mean reward at s(0).
  • The analysis bounds optimal-node failures using P(U_h,i(n) ≤ f*) ≤ β1 n^(α−1).
  • For suboptimal nodes, the proof combines concentration inequalities, visit-count thresholds, union bounds, and the HOO tree structure to control excessive exploration.The argument separately handles nodes whose gaps exceed ν1ρ^h and uses auxiliary lemmas for their confidence and visitation events.
  • B-values are monotone along root-to-leaf paths, enabling the proof to show that suboptimal nodes cannot continue receiving visits when an optimal ancestor has a larger optimistic value.The events E1 and E2 imply a visit-count bound for the suboptimal node through this monotonicity.
  • The proof retains constant factors β1 and β2 only up to multiplicative constants, setting them to one in later uses without changing the main results beyond a constant factor.

E Details of the Simulations

The experiments evaluate POLY-HOOT against continuous-action MCTS baselines on three control tasks, with additional studies examining simulation budgets and discretization sensitivity.

  • Experimental setup: The experiments compare POLY-HOOT with discretized-action UCT, PUCT with progressive widening, and logarithmic-bonus HOOT on continuous-control benchmarks.The benchmarks are CartPole, Inverted Pendulum Swing-up, and LunarLander; CartPole-IG is a harder CartPole variant with increased gravity and altered physical parameters.
  • Experimental setup: The main evaluation uses MCTS depth D = 50 and 100 simulations per state, increasing depth to D = 100 for LunarLander because the task takes longer to finish.
  • Simulation-budget analysis: HOOT and POLY-HOOT require significantly fewer simulation rounds to achieve optimal rewards than discretized-UCT and PUCT, suggesting better sample complexities.This comparison is made using reward versus simulation rounds on CartPole and CartPole-IG.
  • Discretization sensitivity: Discretized-UCT performance does not necessarily improve with finer action granularity and can fluctuate substantially after small changes in discretization level.With a fixed sample budget, larger discretized action sets make individual actions harder to estimate and exploit, motivating adaptive partitioning.
Loading 2006.04672v2…