論文の概要: Constrained Pure Exploration Multi-Armed Bandits with a Fixed Budget
- arxiv url: http://arxiv.org/abs/2211.14768v1
- Date: Sun, 27 Nov 2022 08:58:16 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-29 16:16:37.166292
- Title: Constrained Pure Exploration Multi-Armed Bandits with a Fixed Budget
- Title（参考訳）: 固定予算の制約付き純粋探査型多武装バンディット
- Authors: Fathima Zarin Faizal, Jayakrishnan Nair
- Abstract要約: 固定予算の下で、制約のある純粋な探索、多武装バンディットの定式化を検討する。
本稿では,Successive Rejects フレームワークに基づく textscConstrained-SR というアルゴリズムを提案する。
また, ある特別な場合において, 関連する崩壊速度は情報理論的下界に対してほぼ最適であることを示した。
- 参考スコア（独自算出の注目度）: 4.226118870861363
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a constrained, pure exploration, stochastic multi-armed bandit
formulation under a fixed budget. Each arm is associated with an unknown,
possibly multi-dimensional distribution and is described by multiple attributes
that are a function of this distribution. The aim is to optimize a particular
attribute subject to user-defined constraints on the other attributes. This
framework models applications such as financial portfolio optimization, where
it is natural to perform risk-constrained maximization of mean return. We
assume that the attributes can be estimated using samples from the arms'
distributions and that these estimators satisfy suitable concentration
inequalities. We propose an algorithm called \textsc{Constrained-SR} based on
the Successive Rejects framework, which recommends an optimal arm and flags the
instance as being feasible or infeasible. A key feature of this algorithm is
that it is designed on the basis of an information theoretic lower bound for
two-armed instances. We characterize an instance-dependent upper bound on the
probability of error under \textsc{Constrained-SR}, that decays exponentially
with respect to the budget. We further show that the associated decay rate is
nearly optimal relative to an information theoretic lower bound in certain
special cases.
- Abstract（参考訳）: 固定予算の下で、制約のある純粋な探索、確率的マルチアームバンディットの定式化を検討する。
各アームは未知の多次元分布と関連付けられ、この分布の関数である複数の属性によって記述される。
その目的は、ユーザが定義した他の属性の制約に従う特定の属性を最適化することである。
このフレームワークは、リスクに制約された平均戻り値の最大化を実行するのが自然である金融ポートフォリオ最適化のようなアプリケーションをモデル化する。
これらの属性は腕の分布のサンプルを用いて推定でき、これらの推定器は適切な濃度不等式を満たすと仮定する。
本稿では,Successive Rejects フレームワークをベースとした \textsc{Constrained-SR} というアルゴリズムを提案する。
このアルゴリズムの重要な特徴は、二本腕のインスタンスに対する情報理論の下限に基づいて設計されていることである。
我々は、予算に関して指数関数的に減衰する「textsc{Constrained-SR}」の下で、エラーの確率のインスタンス依存上界を特徴づける。
さらに, ある特別な場合において, 関連する崩壊速度は情報理論的下界に対してほぼ最適であることを示す。
関連論文リスト
- Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget [6.22018632187078]
固定予算の制約付きベスト・ミックスアーム識別(CBMAI)問題を導入する。
目標は、与えられた学習予算$N$で、期待されるコストの制約によって期待される報酬を最大化する最高の混合アームを見つけることである。
我々は、(最良の混合アームの支持の)誤識別に関する理論上の上限を提供し、予算$N$で指数関数的に崩壊することを示す。
論文 参考訳（メタデータ） (2024-05-23T22:35:11Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
確率に基づく推論の原理を再検討し、確率比を用いて妥当な信頼シーケンスを構築することを提案する。
本手法は, 精度の高い問題に特に適している。
提案手法は,オンライン凸最適化への接続に光を当てることにより,推定器の最適シーケンスを確実に選択する方法を示す。
論文 参考訳（メタデータ） (2023-11-08T00:10:21Z) - Complexity Analysis of a Countable-armed Bandit Problem [9.163501953373068]
遊びの地平線上で期待される累積的後悔を最小限に抑えるという古典的問題を考察する。
我々は、$K=2$のとき、$mathcalOleft(log n right)$の率最適有限時間インスタンス依存後悔を実現するアルゴリズムを提案する。
問題に対する後悔の順序と複雑さは、古典的MAB問題と非常に類似していることを示しているが、アルゴリズム設計における性能境界の特性と健全な側面は、後者とはかなり異なる。
論文 参考訳（メタデータ） (2023-01-18T00:53:46Z) - Quantization for decentralized learning under subspace constraints [61.59416703323886]
エージェントがサブスペース制約を最小化するために個々のコスト関数を持つ分散最適化問題を考察する。
本稿では,エージェントが確率化量子化器を用いて推定値を圧縮する適応分散型戦略を提案し,検討する。
この分析は、量子化ノイズのいくつかの一般的な条件下では、平均二乗誤差と平均ビットレートの両方で戦略が安定であることを示している。
論文 参考訳（メタデータ） (2022-09-16T09:38:38Z) - From Optimality to Robustness: Dirichlet Sampling Strategies in
Stochastic Bandits [0.0]
本研究では、腕の観察を再サンプリングした経験的指標のペア比較に基づいて、ジェネリックディリクレサンプリング(DS)アルゴリズムについて検討する。
この戦略の異なる変種は、分布が有界であるときに証明可能な最適後悔保証と、半有界分布に対して軽度量子状態の対数後悔を実現することを示す。
論文 参考訳（メタデータ） (2021-11-18T14:34:21Z) - Deconfounding Scores: Feature Representations for Causal Effect
Estimation with Weak Overlap [140.98628848491146]
推定対象の偏りを伴わずに高い重なりを生じさせる,デコンファウンディングスコアを導入する。
分離スコアは観測データで識別可能なゼロ共分散条件を満たすことを示す。
特に,この手法が標準正規化の魅力的な代替となることを示す。
論文 参考訳（メタデータ） (2021-04-12T18:50:11Z) - Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed
Rewards [24.983866845065926]
我々は、重い尾の報酬を持つマルチアームのバンディットを考えており、そのp$-thのモーメントは、定数$nu_p$が1pleq2$である。
本稿では,従来の情報として$nu_p$を必要としない新しいロバストな推定器を提案する。
提案した推定器の誤差確率は指数関数的に高速に減衰することを示す。
論文 参考訳（メタデータ） (2020-10-24T10:44:02Z) - Statistically Robust, Risk-Averse Best Arm Identification in Multi-Armed
Bandits [4.760079434948198]
このようなパラメトリック情報を利用する特殊なアルゴリズムは、パラメータが誤って特定された場合、不整合学習性能が高いことを示す。
主な貢献は, (i) 固定予算純探索条件下で統計的に堅牢なMABアルゴリズムの基本的な性能限界を確立すること, (ii) 二つの近似アルゴリズムのクラスを提案することである。
論文 参考訳（メタデータ） (2020-08-28T13:43:12Z) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳（メタデータ） (2020-03-05T21:29:27Z) - Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
確率分布が未知な分布の不確実性の下でBQOについて検討する。
標準的なBQOアプローチは、固定されたサンプル集合が与えられたときの真の期待目標のモンテカルロ推定を最大化する。
この目的のために,新しい後方サンプリングに基づくアルゴリズム,すなわち分布的に堅牢なBQO(DRBQO)を提案する。
論文 参考訳（メタデータ） (2020-01-19T12:00:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。