$\varepsilon$-Good Action Identification in Fixed-Budget Monte Carlo Tree Search

• URL: http://arxiv.org/abs/2605.11324v1
• Date: Mon, 11 May 2026 23:21:32 GMT
• Title: $\varepsilon$-Good Action Identification in Fixed-Budget Monte Carlo Tree Search
• Abstract summary: We study the fixed-budget max-min action identification problem in depth-2 max-min trees.<n>We give a new $varepsilon$-good guarantee for Successive Rejects.<n>This is the first provable fixed-budget guarantee for max-min action identification.
• Score: 23.84300743927881
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the fixed-budget max-min action identification problem in depth-2 max-min trees, an important special case of Monte Carlo Tree Search. A learner sequentially allocates $T$ samples to leaves and then recommends a subtree whose minimum leaf value is largest. Motivated by approximate planning, we focus on $\varepsilon$-good subtree identification, where any subtree whose min value is within $\varepsilon$ of the optimal maximin value is acceptable. Our main contribution is an $\varepsilon$-agnostic algorithm: it does not require $\varepsilon$ as input, but achieves instance-dependent error bounds for every meaningful $\varepsilon$. We show that the misidentification probability decays as $\exp(-\widetildeΘ(T/H_2(\varepsilon)))$, where $H_2(\varepsilon)$ captures both cross-subtree and within-subtree gaps. When each subtree has a single leaf, the problem reduces to standard fixed-budget best-arm identification, and our analysis recovers, up to accelerating factors, known $\varepsilon$-good guarantees for halving-style methods while giving a new $\varepsilon$-good guarantee for Successive Rejects. On the lower-bound side, we provide complementary positive and negative results showing that max-min identification has a different hardness structure from standard $K$-armed bandits. To our knowledge, this is the first provable fixed-budget algorithmic guarantee for max-min action identification.

Related papers

• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
  We propose a piecewise stationary linear bandit (PSLB) model where the quality of an arm is measured by its return averaged over all contexts. PS$varepsilon$BAI$+$ is guaranteed to identify an $varepsilon$-optimal arm with probability $ge 1-delta$ and with a minimal number of samples.
  arXiv  Detail & Related papers  (2024-10-10T06:15:42Z)
• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
  We present efficient algorithms for policy evaluation, best policy identification and regret minimization. For policy evaluation and best policy identification, we show that our algorithms are nearly minimax optimal. All the proposed algorithms consist of two phases: they first leverage spectral methods to estimate the left and right singular subspaces of the low-rank reward matrix.
  arXiv  Detail & Related papers  (2024-02-24T06:36:08Z)
• Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time Guarantees [3.5509551353363644]
  We give the first algorithm that maintains an approximate decision tree over an arbitrary sequence of insertions and deletions of labeled examples. We provide a deterministic algorithm that maintains an $epsilon$-approximate tree using $O!left(fracd, f(n)n operatornamepolyfrachepsilonright)$ operations per update.
  arXiv  Detail & Related papers  (2023-02-08T11:02:58Z)
• Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
  We study risk-sensitive Reinforcement Learning (RL), focusing on the objective of Conditional Value at Risk (CVaR) with risk tolerance $tau$. We show the minimax CVaR regret rate is $Omega(sqrttau-1AK)$, where $A$ is the number of actions and $K$ is the number of episodes. We show that our algorithm achieves the optimal regret of $widetilde O(tau-1sqrtSAK)$ under a continuity assumption and in general attains a near
  arXiv  Detail & Related papers  (2023-02-07T02:22:31Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• Coresets for Decision Trees of Signals [19.537354146654845]
  We provide the first algorithm that outputs such a $(k,varepsilon)$-coreset for emphevery such matrix $D$. This is by forging a link between decision trees from machine learning -- to partition trees in computational geometry.
  arXiv  Detail & Related papers  (2021-10-07T05:49:55Z)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  We learn the set of $epsilon$-optimal goal-conditioned policies attaining all states that are incrementally reachable within $L$ steps. DisCo is the first algorithm that can return an $epsilon/c_min$-optimal policy for any cost-sensitive shortest-path problem.
  arXiv  Detail & Related papers  (2020-12-29T14:06:09Z)
• Testing and reconstruction via decision trees [19.304587350775385]
  We study sublinear and local computation algorithms for decision trees, focusing on testing and reconstruction. A tester that runs in $mathrmpoly(log s, 1/varepsilon)cdot nlog n$ time makes $mathrmpoly(log s,1/varepsilon)cdot n$ queries to an unknown function.
  arXiv  Detail & Related papers  (2020-12-16T04:18:00Z)
• Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu [14.298220510927695]
  We provide finite sample guarantees for the classical ChowLiu algorithm (IEEE Trans.Inform.Theory, 1968) We show that for a specific tree $T$, with $widetildeO (|Sigma|2nvarepsilon-1)$ samples from a distribution $P$ over $Sigman$, one can efficiently learn the closest KL divergence.
  arXiv  Detail & Related papers  (2020-11-09T02:08:56Z)
• Provable guarantees for decision tree induction: the agnostic setting [16.784355746717562]
  We give strengthened provable guarantees on the performance of widely employed and empirically successful sl top-down decision tree learnings. We show that for all monotone functions$f$ and parameters $sin mathN$, theses construct a decision tree of size $stildeO((log s)/varepsilon2)$ that achieves error. We complement our algorithmic guarantee with a near-matching $stildeOmega(log s)$ lower bound.
  arXiv  Detail & Related papers  (2020-06-01T06:44:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.