論文の概要: Stochastically Constrained Best Arm Identification with Thompson Sampling
- arxiv url: http://arxiv.org/abs/2501.03877v1
- Date: Tue, 07 Jan 2025 15:40:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-08 15:47:02.532760
- Title: Stochastically Constrained Best Arm Identification with Thompson Sampling
- Title(参考訳): トンプソンサンプリングを用いた統計的に制約されたベストアーム同定
- Authors: Le Yang, Siyang Gao, Cheng Li, Yi Wang,
- Abstract要約: 制約が存在する場合の最適な腕識別の問題について考察する。
我々は、この問題を解決する手段として、トンプソンサンプリング(TS)の一般的なアイデアを探求する。
我々は、TSに基づくサンプリングアルゴリズムを設計し、後方収束率の最適性を確立し、数値例を用いてその優れた性能を示す。
- 参考スコア(独自算出の注目度): 11.728338956484091
- License:
- Abstract: We consider the problem of the best arm identification in the presence of stochastic constraints, where there is a finite number of arms associated with multiple performance measures. The goal is to identify the arm that optimizes the objective measure subject to constraints on the remaining measures. We will explore the popular idea of Thompson sampling (TS) as a means to solve it. To the best of our knowledge, it is the first attempt to extend TS to this problem. We will design a TS-based sampling algorithm, establish its asymptotic optimality in the rate of posterior convergence, and demonstrate its superior performance using numerical examples.
- Abstract(参考訳): 確率的制約が存在する場合の最適な腕識別の問題について考察する。
目標は、残りの措置の制約を受ける客観的尺度を最適化するアームを特定することである。
我々は、この問題を解決する手段として、トンプソンサンプリング(TS)の一般的なアイデアを探求する。
我々の知る限りでは、TSをこの問題に拡張する最初の試みである。
我々は、TSに基づくサンプリングアルゴリズムを設計し、後方収束率の漸近的最適性を確立し、数値例を用いてその優れた性能を示す。
関連論文リスト
- Reward Maximization for Pure Exploration: Minimax Optimal Good Arm Identification for Nonparametric Multi-Armed Bandits [35.35226227009685]
グッドアーム識別(グッドアームアイソレーション、英: Good Arm Identification、IGA)は、腕をできるだけ早くしきい値以上の手段でラベル付けすることを目的とした、実用的なバンドイット推論の目的である。
本稿では,報奨最大化サンプリングアルゴリズムと新たな非有意シーケンシャルテストを組み合わせることで,GAを効率よく解くことができることを示す。
我々の実験結果は、ミニマックス設定を超えるアプローチを検証し、すべての停止時間におけるサンプルの期待数を、合成および実世界の設定で少なくとも50%削減する。
論文 参考訳(メタデータ) (2024-10-21T01:19:23Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Thompson Exploration with Best Challenger Rule in Best Arm
Identification [66.33448474838342]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳(メタデータ) (2023-10-01T01:37:02Z) - Optimality of Thompson Sampling with Noninformative Priors for Pareto
Bandits [81.45853204922795]
トンプソンサンプリングは、いくつかの報酬モデルにおいて問題依存の低い境界を達成することが示されている。
重い尾を持つパレートモデルに対するTSの最適性は、2つの未知のパラメータによってパラメータ化される。
ジェフリーズおよび参照先行値を持つTSは、トラルニケート手順を使用すると、下界を達成できる。
論文 参考訳(メタデータ) (2023-02-03T04:47:14Z) - SPRT-based Efficient Best Arm Identification in Stochastic Bandits [31.359578768463752]
本稿では,固定信頼度設定におけるマルチアームバンディットの腕識別問題について検討する。
バンドイットの指数族に対する既存のアルゴリズムは計算上の課題に直面している。
逐次テストに有効であることが知られている確率比ベースのテストを採用するフレームワークが提案されている。
論文 参考訳(メタデータ) (2022-07-22T15:54:53Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳(メタデータ) (2021-11-14T21:49:58Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳(メタデータ) (2020-06-29T14:25:51Z) - Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a
Differentially Private Scheme [16.1694012177079]
我々は,多腕バンディットにおける最高の武器識別問題,潜在的に私的な報酬について検討する。
ゴールは、固定された所定のレベルで、最も高い定量値を持つ腕を特定することである。
このアルゴリズムは$delta$-PACであり,サンプルの複雑さを特徴付ける。
論文 参考訳(メタデータ) (2020-06-11T20:23:43Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳(メタデータ) (2017-02-16T23:42:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。