論文の概要: Budgeted Bayesian Bandits for Future Utilization
- arxiv url: http://arxiv.org/abs/2610.24156v1
- Date: Fri, 16 Oct 2026 19:29:48 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-26 10:35:55.524934
- Title: Budgeted Bayesian Bandits for Future Utilization
- Title（参考訳）: ベイジアンバンドの予算化と今後の活用
- Abstract要約: 我々は、探査が厳しい予算を持ち、搾取に先立つ変種について研究する。
両アルゴリズムは, 緩和が原始的精度である場合でも, 解析が厳密であることを示す。
次に、非消滅状態における交換可能な観測のために、1-e-1近似0.63を保証できる効率的なアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The multi-armed bandit problem models the trade-off between exploration and exploitation. In this paper, we study the variant where exploration has a hard budget and precedes exploitation. Prior guarantees include a 1/3 approximation by Guha and Munagala using Lagrangian duality, and a 4/27 approximation by Ma against a primal linear programming relaxation for a more general model. We show that the analyses of both algorithms are tight, even when their relaxations are asymptotically exact. We provide a different efficient algorithm that achieves a 0.43 approximation. We then provide an efficient algorithm whose guarantee approaches 1-e^{-1} approx 0.63 for bounded exchangeable reward observations in a non-vanishing regime, which is asymptotically tight against natural linear programming relaxations. The technique also gives certificates for stopping sequential model evaluation.
- Abstract（参考訳）: 多武装の盗賊問題は、探索と搾取の間のトレードオフをモデル化する。
本稿では,探査に予算がかかり,利用に先立つ形態について検討する。
以前の保証には、ラグランジュ双対性を用いたGuhaとMunagalaによる1/3の近似、より一般的なモデルに対する原始線形プログラミング緩和に対するMaによる4/27の近似が含まれる。
両アルゴリズムの緩和が漸近的に正確である場合でも,解析は厳密であることを示す。
我々は0.43近似を達成する異なる効率的なアルゴリズムを提供する。
次に, 線形プログラミング緩和に対して漸近的に厳密な非消滅状態における有界交換型報酬観測に対して, 1-e^{-1} 近似 0.63 に近似した効率的なアルゴリズムを提案する。
この技術は、シーケンシャルモデル評価を止めるための証明書も提供する。
関連論文リスト
- Computation-Utility-Privacy Tradeoffs in Bayesian Estimation [14.293470686822305]
平均二乗誤差を実現する2つの問題に対して,最初の効率的なアルゴリズムを提案する。
我々は、プライベートベイズ最適推定を実現するために、arXiv:2212.05のプライバシーとロバスト性に関するフレームワークを取り上げている。
また、ショートフラット分解に基づく新しい種類の制約を平方和ツールキットに追加する。
論文 参考訳（メタデータ） (2026-03-18T20:20:58Z) - Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。
我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
論文 参考訳（メタデータ） (2025-06-03T02:56:26Z) - Regret Minimization and Statistical Inference in Online Decision Making with High-dimensional Covariates [7.21848268647674]
我々は、決定のための$varepsilon$-greedybanditアルゴリズムと、疎帯域パラメータを推定するためのハードしきい値アルゴリズムを統合する。
マージン条件下では、我々の手法は、$O(T1/2)$ regret あるいは古典的な$O(T1/2)$-consistent推論のいずれかを達成する。
論文 参考訳（メタデータ） (2024-11-10T01:47:11Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - The Stochastic Proximal Distance Algorithm [5.3315823983402755]
本稿では,所望の制約付き推定問題をペナルティパラメータとして回復する反復最適化手法のクラスを提案し,解析する。
我々は、最近の理論装置を拡張して有限誤差境界を確立し、収束率の完全な評価を行う。
また,本手法が一般的な学習課題のバッチバージョンより優れていることを示す。
論文 参考訳（メタデータ） (2022-10-21T22:07:28Z) - Residual Overfit Method of Exploration [78.07532520582313]
提案手法は,2点推定値の調整と1点オーバーフィットに基づく近似探索手法を提案する。
このアプローチは、調整されたモデルと比較して、オーバーフィットモデルが最も過度な適合を示すアクションへの探索を促進する。
ROMEを3つのデータセット上の確立されたコンテキスト的帯域幅法と比較し、最も優れたパフォーマンスの1つとみなす。
論文 参考訳（メタデータ） (2021-10-06T17:05:33Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。
MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
論文 参考訳（メタデータ） (2020-10-12T17:41:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。