論文の概要: Nearly Optimal Best Arm Identification for Semiparametric Bandits
- arxiv url: http://arxiv.org/abs/2604.03969v1
- Date: Sun, 05 Apr 2026 05:13:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-07 15:49:18.854212
- Title: Nearly Optimal Best Arm Identification for Semiparametric Bandits
- Title（参考訳）: 半パラメトリック帯域に対する準最適腕同定法
- Authors: Seok-Jin Kim,
- Abstract要約: 半パラメトリックバンディットにおける固定信頼ベストアーム識別(BAI)について検討した。
トランスダクティブ・セッティングのために、シフトした特徴に対する対応する線形帯域複雑性を特徴とする、達成可能なインスタンス依存下界を確立する。
我々の分析は、最大ログ係数と追加の$d2$項を含む、ほぼ最適に高確率のサンプル複雑度上限を得る。
- 参考スコア（独自算出の注目度）: 2.538209532048867
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study fixed-confidence Best Arm Identification (BAI) in semiparametric bandits, where rewards are linear in arm features plus an unknown additive baseline shift. Unlike linear-bandit BAI, this setting requires orthogonalized regression, and its instance-optimal sample complexity has remained open. For the transductive setting, we establish an attainable instance-dependent lower bound characterized by the corresponding linear-bandit complexity on shifted features. We then propose a computationally efficient phase-elimination algorithm based on a new $XY$-design for orthogonalized regression. Our analysis yields a nearly optimal high-probability sample-complexity upper bound, up to log factors and an additive $d^2$ term, and experiments on synthetic instances and the Jester dataset show clear gains over prior baselines.
- Abstract（参考訳）: 半パラメトリックバンディットにおける固定信頼ベストアーム識別(BAI)について検討した。
線形帯域BAIとは異なり、この設定は直交回帰を必要とする。
トランスダクティブ・セッティングのために、シフトした特徴に対する対応する線形帯域複雑性を特徴とする、達成可能なインスタンス依存下界を確立する。
次に、直交回帰のための新しい$XY$-designに基づく計算効率の良い位相除去アルゴリズムを提案する。
分析の結果,最大ログ係数と追加の$d^2$項を含む,ほぼ最適な高確率試料複雑度上界が得られた。
関連論文リスト
- EVaR-Optimal Arm Identification in Bandits [7.340828059560291]
The fixed-confidence best arm identification problem in the multiarmed bandit (MAB) framework under the Entropic Value-at-Risk criterion。
論文 参考訳（メタデータ） (2025-10-06T11:49:56Z) - Identifying All ε-Best Arms in (Misspecified) Linear Bandits [9.638337713545065]
LinFACT (LinFACT) は、リニアバンディットにおける全てのエプシロンベストアームの識別を最適化するために設計されたアルゴリズムである。
我々は、LinFACTが、この下界を対数係数にマッチングすることで、インスタンス最適性を達成することを示す。
合成および実薬品発見データを含む数値実験により、LinFACTはサンプルの複雑さを減らしたより有望な候補を同定することを示した。
論文 参考訳（メタデータ） (2025-09-29T22:26:52Z) - Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。
我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
論文 参考訳（メタデータ） (2025-06-03T02:56:26Z) - Sample Complexity of Linear Quadratic Regulator Without Initial Stability [7.245261469258501]
ReINFORCEにインスパイアされ、未知のダイナミクスを持つ線形二次レギュレータ(LQR)問題に対して、新しいリリーディングホライゾンアルゴリズムを導入する。
従来の手法とは異なり、本アルゴリズムはサンプルの複雑さの順序を同じに保ちながら、2点勾配推定に依存することを回避している。
論文 参考訳（メタデータ） (2025-02-20T02:44:25Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
本稿では,テクスト幾何学的強単調ゲームに対する新たな収束結果を確立する。
我々のキーとなる結果は、RGDがテクスト幾何学的手法で最終定位線形収束を実現することを示しています。
全体として、ユークリッド設定を超えるゲームに対して、幾何学的に非依存な最終点収束解析を初めて提示する。
論文 参考訳（メタデータ） (2023-06-29T01:20:44Z) - Efficient and Near-Optimal Smoothed Online Learning for Generalized
Linear Functions [28.30744223973527]
我々は,K-wise線形分類において,統計学的に最適なログ(T/sigma)の後悔を初めて楽しむ計算効率のよいアルゴリズムを提案する。
一般化線形分類器によって誘導される不一致領域の幾何学の新たな特徴付けを開発する。
論文 参考訳（メタデータ） (2022-05-25T21:31:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。