論文の概要: An Efficient Algorithm for Thresholding Monte Carlo Tree Search
- arxiv url: http://arxiv.org/abs/2601.22600v1
- Date: Fri, 30 Jan 2026 05:50:04 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-02 18:28:15.258489
- Title: An Efficient Algorithm for Thresholding Monte Carlo Tree Search
- Title（参考訳）: モンテカルロ木探索のための効率的なアルゴリズム
- Authors: Shoma Nameki, Atsuyoshi Nakamura, Junpei Komiyama, Koji Tabata,
- Abstract要約: 本稿では,Thresholding Monte Carlo Tree Search問題を紹介する。
我々はトラック・アンド・ストップ戦略に基づく$$$-correct sequence sampleアルゴリズムを開発した。
そこで本研究では, D-Tracking アーム推進戦略の比に基づく修正により, 実験試料の複雑さが大幅に向上したことを示す。
- 参考スコア（独自算出の注目度）: 5.983611749323508
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce the Thresholding Monte Carlo Tree Search problem, in which, given a tree $\mathcal{T}$ and a threshold $θ$, a player must answer whether the root node value of $\mathcal{T}$ is at least $θ$ or not. In the given tree, `MAX' or `MIN' is labeled on each internal node, and the value of a `MAX'-labeled (`MIN'-labeled) internal node is the maximum (minimum) of its child values. The value of a leaf node is the mean reward of an unknown distribution, from which the player can sample rewards. For this problem, we develop a $δ$-correct sequential sampling algorithm based on the Track-and-Stop strategy that has asymptotically optimal sample complexity. We show that a ratio-based modification of the D-Tracking arm-pulling strategy leads to a substantial improvement in empirical sample complexity, as well as reducing the per-round computational cost from linear to logarithmic in the number of arms.
- Abstract（参考訳）: 我々はThresholding Monte Carlo Tree Search問題を導入し、ツリー$\mathcal{T}$としきい値$θ$が与えられた場合、プレイヤーは、ルートノード値$\mathcal{T}$が少なくとも$θ$であるかどうかを答えなければならない。
与えられた木において、「MAX」または「MIN」は各内部ノードにラベル付けされ、「MAX」ラベル付き(`MIN'ラベル付き)内部ノードの値は、その子値の最大(最小)である。
リーフノードの値は未知の分布の平均報酬であり、そこからプレイヤーは報酬をサンプリングすることができる。
そこで本研究では,漸近的に最適なサンプル複雑性を持つトラック・アンド・ストップ戦略に基づく,$δ$-correct sequence sampleアルゴリズムを開発した。
そこで本研究では, D-Tracking アームプーリング戦略の比に基づく修正により, 実験サンプルの複雑性が大幅に向上し, アーム数に対する計算コストが線形から対数に減少することを示した。
関連論文リスト
- Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity [14.396304498754688]
私たちは、$(lambda, beta)$-sparsityをダブした、空白という新しい概念を示します。
つまり、少なくとも$theta$のリスクが他のグループのリスクよりも少なくとも$lambda$であるような、少なくとも$beta$グループのセットがあります。
計算効率のよい手法により,次元自由な半適応サンプルの複雑性を得る方法を示す。
論文 参考訳（メタデータ） (2024-10-01T13:45:55Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。
各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。
第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。
我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
論文 参考訳（メタデータ） (2020-06-11T00:55:35Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-02T16:38:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。