論文の概要: Tight Sample Complexity Bounds for Best-Arm Identification Under Bounded Systematic Bias

• arxiv url: http://arxiv.org/abs/2604.14345v2
• Date: Fri, 17 Apr 2026 18:07:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-21 13:51:31.117152
• Title: Tight Sample Complexity Bounds for Best-Arm Identification Under Bounded Systematic Bias
• Title（参考訳）: 境界系バイアス下でのベストアーム同定のためのTight Sample Complexity bounds
• Authors: Tianhao Qian,
• Abstract要約: 本稿では,ノード展開過程を動的フロンティア上での局所的BAI(Best-Arm Identification)問題とする。 Lambert W 関数を反転させることで $mathcalO((-4L)-2)$ の加法的なサンプル複雑性を確立し、これは経験的報酬ギャップが 4L$ を超える場合にのみ安全なノードの除去が可能であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: As search depth increases in autonomous reasoning and embodied planning, the candidate action space expands exponentially, heavily taxing computational budgets. While heuristic pruning is a common countermeasure, it operates without formal safety guarantees when surrogate models (like LLMs) exhibit systematic evaluation biases. This paper frames the node expansion process as a localized Best-Arm Identification (BAI) problem over dynamic frontiers, subject to a bounded systematic bias $L$. By inverting the Lambert W function, we establish an additive sample complexity of $\mathcal{O}((Δ-4L)^{-2})$, which indicates that safe node elimination is only feasible when the empirical reward gap exceeds $4L$. We complement this with an information-theoretic lower bound of $Ω((Δ-2L)^{-2})$ to confirm the structural limits of biased search. Subsequent evaluations on both synthetic trees and complex reasoning tasks demonstrate that adhering to this local safety boundary successfully preserves optimal trajectories while maximizing sample allocation efficiency.
• Abstract（参考訳）: 自律的推論と具体化計画において探索深度が増加するにつれて、候補行動空間は指数関数的に拡大し、計算予算に重税を課す。 ヒューリスティックプルーニングは一般的な対策であるが、Surrogateモデル(LLMなど)が体系的な評価バイアスを示す場合、公式な安全保証なしで機能する。 本稿では, ノード展開過程を, 動的フロンティア上の局所的ベストアーム同定(BAI)問題として, 有界な系統的バイアス$L$で表す。 Lambert W 関数を反転させることで、$\mathcal{O}((Δ-4L)^{-2})$ の加法的なサンプル複雑性を確立する。 これを情報理論的下界の$Ω((Δ-2L)^{-2})$で補い、バイアス探索の構造的限界を確かめる。 合成木と複雑な推論タスクの両方に対するその後の評価は、この局所的な安全境界に付着することで、標本割り当て効率を最大化しながら最適な軌道を維持できることを示した。

関連論文リスト

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
  我々は、s-正方形および非正方形不確実性集合の下で、一般的な政策パラメータ化を伴うロバストマルコフ決定過程(RMDP)について検討する。 無限状態空間に拡張する一般政策パラメタライゼーションに対する新しいリプシッツ・リプシッツ・スムースネス特性を証明した。 本研究では,S-正方形不確かさに対する勾配降下アルゴリズムと非正方形不確かさに対するFrank-Wolfeアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2026-02-11T21:44:20Z)
• Blind Inverse Game Theory: Jointly Decoding Rewards and Rationality in Entropy-Regularized Competitive Games [0.0]
  観測行動から$theta$と$tau$を共同で回収する最初の統計フレームワークであるBlind-IGTを紹介する。 結合パラメータの回復に最適な$mathcalO(N-1/2)$収束率を達成できることを示す。 フレームワークをマルコフゲームに拡張し、強い経験的性能で最適な収束率を示す。
  論文  参考訳（メタデータ） (2025-11-07T16:27:59Z)
• Scalable Neural Incentive Design with Parameterized Mean-Field Approximation [28.20524168049273]
  力学と報酬がリプシッツであるとき、有限$N$ ID の目標は、PMFG によって $mathscrO(frac1sqrtN)$ で近似されることを示す。 さらに、反復平衡作用素の明示的な微分を利用して勾配を効率的に計算する、随伴平均集中設計(AMID)アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2025-10-24T13:18:54Z)
• Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilities [12.104551746465932]
  安全マルチエージェント強化学習について検討し、エージェントはそれぞれの安全制約を満たしつつ、局所的な目的の総和をまとめて最大化しようとする。 我々のアルゴリズムは、$mathcalOleft(T-2/3right)$のレートで1次定常点(FOSP)に収束する。 サンプルベースの設定では、高い確率で、我々のアルゴリズムは、$epsilon$-FOSPを達成するために$widetildemathcalOleft(epsilon-3.5right)$サンプルが必要です。
  論文  参考訳（メタデータ） (2023-05-27T20:08:35Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。 我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。 我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
  論文  参考訳（メタデータ） (2023-03-17T17:53:28Z)
• LSDAT: Low-Rank and Sparse Decomposition for Decision-based Adversarial Attack [74.5144793386864]
  LSDATは、入力サンプルのスパース成分と対向サンプルのスパース成分によって形成される低次元部分空間における摂動を加工する。 LSDは画像ピクセル領域で直接動作し、スパース性などの非$ell$制約が満たされることを保証します。
  論文  参考訳（メタデータ） (2021-03-19T13:10:47Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。 本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-03-01T17:47:03Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。