論文の概要: $\varepsilon$-Good Action Identification in Fixed-Budget Monte Carlo Tree Search
- arxiv url: http://arxiv.org/abs/2605.11324v1
- Date: Mon, 11 May 2026 23:21:32 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-13 21:48:56.47407
- Title: $\varepsilon$-Good Action Identification in Fixed-Budget Monte Carlo Tree Search
- Title（参考訳）: 固定予算モンテカルロ木探索における$\varepsilon$-Good行動同定
- Authors: Yinan Li, Tuan Nguyen, Kwang-Sung Jun,
- Abstract要約: 深さ2の最大ミン木における固定予算最大ミン作用同定問題について検討した。
新しい$varepsilon$-good guarantee for Successive Rejectsを与えます。
これは、最大ミンアクション識別のための最初の証明可能な固定予算保証である。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: モンテカルロ木探索の重要な事例である深さ2の最大値木における固定予算最大値行動同定問題について検討した。
学習者は、葉に$T$サンプルを順次割り当て、最小の葉値が最大となるサブツリーを推奨する。
ここでは、min値が$\varepsilon$の任意のサブツリーが、最適なmaximin値の$\varepsilon$の範囲内で許容されるような、$\varepsilon$-goodサブツリー識別に焦点を当てる。
入力として$\varepsilon$を必要としないが、意味のある$\varepsilon$に対してインスタンス依存のエラーバウンダリを達成する。
誤同定確率は $\exp(-\widetilde )(T/H_2(\varepsilon))$, ここでは$H_2(\varepsilon)$ はクロス・サブツリーとイン・サブツリーのギャップを捕捉する。
各サブツリーが1つの葉を持つ場合、問題は標準の固定予算のベストアーム識別に還元され、我々の分析は、継承リジェクトに対する新しい$\varepsilon$-goodの保証を提供しながら、半減型メソッドに対する$\varepsilon$-goodの保証として知られる、加速する要因まで回復する。
低バウンド側では、最大ミン識別が標準の$K$腕の包帯と異なる硬度構造を持つことを示す相補的正および負の結果を提供する。
我々の知る限り、これは最大ミンアクション識別のための証明可能な固定予算アルゴリズムの保証である。
関連論文リスト
- Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
そこで本研究では,各文脈の平均値によって腕の質を計測するPSLBモデルを提案する。
PS$varepsilon$BAI$+$は、$varepsilon$-optimal armを、確率$ge 1-delta$と最小限のサンプルで識別することが保証される。
論文 参考訳（メタデータ） (2024-10-10T06:15:42Z) - Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。
政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。
提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
論文 参考訳（メタデータ） (2024-02-24T06:36:08Z) - Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time
Guarantees [3.5509551353363644]
ラベル付き例の挿入と削除の任意の順序に近似的な決定木を保持する最初のアルゴリズムを与える。
我々は$O!left(fracd, f(n)n operatornamenamepolyfrachepsilonright)$ Operations per updateを使って$epsilon$-approximate treeを維持する決定論的アルゴリズムを提供する。
論文 参考訳（メタデータ） (2023-02-08T11:02:58Z) - Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。
ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。
我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文 参考訳（メタデータ） (2023-02-07T02:22:31Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文 参考訳（メタデータ） (2020-12-29T14:06:09Z) - Testing and reconstruction via decision trees [19.304587350775385]
決定木に対する部分線形および局所計算アルゴリズムを,テストと再構成に焦点をあてて検討した。
mathrmpoly(log s, 1/varepsilon)cdot nlog n$ time で実行するテスターは、未知の関数への$mathrmpoly(log s, 1/varepsilon)cdot n$ queryを作る。
論文 参考訳（メタデータ） (2020-12-16T04:18:00Z) - Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu [14.298220510927695]
古典的ChowLiuアルゴリズム(IEEE Trans.Inform.Theory, 1968)に対する有限サンプル保証を提供する。
特定の木の$T$に対して、$widetildeO (|Sigma|2nvarepsilon-1)$の分布からのサンプルを$P$ over $Sigman$とすると、最も近いKL分岐を効率的に学習できる。
論文 参考訳（メタデータ） (2020-11-09T02:08:56Z) - Provable guarantees for decision tree induction: the agnostic setting [16.784355746717562]
我々は、広く採用され、実証的に成功したトップダウン決定木学習の性能に関する証明可能な保証を与える。
すべてのモノトン関数に対して$f$とパラメータ$sin MathN$は、stildeO((log s)/varepsilon2)$でエラーを発生させる決定木を構成する。
アルゴリズムの保証は、ほぼ一致する$stildeOmega(log s)$ lower boundで補います。
論文 参考訳（メタデータ） (2020-06-01T06:44:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。