論文の概要: Variance-Optimal Arm Selection: Regret Minimization and Best Arm Identification

• arxiv url: http://arxiv.org/abs/2505.11985v2
• Date: Tue, 20 May 2025 17:01:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-21 14:49:52.256853
• Title: Variance-Optimal Arm Selection: Regret Minimization and Best Arm Identification
• Title（参考訳）: 可変最適アーム選択:レグレット最小化とベストアーム識別
• Authors: Sabrina Khurshid, Gourab Ghatak, Mohammad Shahid Abdulla,
• Abstract要約: 我々は、後悔設定のためのtextttUCB-VV と呼ばれるオンラインアルゴリズムを開発し、制限付き報酬に対する後悔の上限が $mathcalOleft(lognright)$として進化することを示す。 我々は, 試料分散に対する新しい濃度不等式を用いて, フレームワークを有界分布から準ガウス分布に拡張する。
• 参考スコア（独自算出の注目度）: 3.5502600490147196
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper focuses on selecting the arm with the highest variance from a set of $K$ independent arms. Specifically, we focus on two settings: (i) regret setting, that penalizes the number of pulls of suboptimal arms in terms of variance, and (ii) fixed-budget BAI setting, that evaluates the ability of an algorithm to determine the arm with the highest variance after a fixed number of pulls. We develop a novel online algorithm called \texttt{UCB-VV} for the regret setting and show that its upper bound on regret for bounded rewards evolves as $\mathcal{O}\left(\log{n}\right)$ where $n$ is the horizon. By deriving the lower bound on the regret, we show that \texttt{UCB-VV} is order optimal. For the fixed budget BAI setting, we propose the \texttt{SHVV} algorithm. We show that the upper bound of the error probability of \texttt{SHVV} evolves as $\exp\left(-\frac{n}{\log(K) H}\right)$, where $H$ represents the complexity of the problem, and this rate matches the corresponding lower bound. We extend the framework from bounded distributions to sub-Gaussian distributions using a novel concentration inequality on the sample variance. Leveraging the same, we derive a concentration inequality for the empirical Sharpe ratio (SR) for sub-Gaussian distributions, which was previously unknown in the literature. Empirical simulations show that \texttt{UCB-VV} consistently outperforms \texttt{$\epsilon$-greedy} across different sub-optimality gaps, though it is surpassed by \texttt{VTS}, which exhibits the lowest regret, albeit lacking in theoretical guarantees. We also illustrate the superior performance of \texttt{SHVV}, for a fixed budget setting under 6 different setups against uniform sampling. Finally, we conduct a case study to empirically evaluate the performance of the \texttt{UCB-VV} and \texttt{SHVV} in call option trading on $100$ stocks generated using geometric Brownian motion (GBM).
• Abstract（参考訳）: 本稿は,K$独立アームの集合から最も分散度の高いアームを選択することに焦点を当てる。 具体的には2つの設定に焦点を当てます。 一 相違の点において、下腕の引っ掛けの数を罰する後悔の設定、 (II)固定予算BAI設定は、一定数のプル後に最も分散したアームを決定するアルゴリズムの能力を評価するものである。 後悔設定のための新しいオンラインアルゴリズムである「texttt{UCB-VV}」を開発し、その上限付き報酬に対する後悔の上限が$\mathcal{O}\left(\log{n}\right)$として進化することを示す。 後悔の下位境界を導出することにより、 \texttt{UCB-VV} が最適であることを示す。 固定予算BAI設定では, texttt{SHVV} アルゴリズムを提案する。 我々は、 \texttt{SHVV} の誤差確率の上界が $\exp\left(-\frac{n}{\log(K) H}\right)$ として進化することを示す。 我々は, 試料分散に対する新しい濃度不等式を用いて, フレームワークを有界分布から準ガウス分布に拡張する。 これを利用して、ガウス以下の分布に対する経験的シャープ比(SR)の濃度不等式を導出した。 経験的シミュレーションにより、 \texttt{UCB-VV} は、理論的な保証が欠如しているにもかかわらず、最も低い後悔を示す \texttt{UCB-VTS} に勝っているにもかかわらず、異なる準最適ギャップにおいて、一貫して \textt{$\epsilon$-greedy} を上回ることを示した。 また, 均一サンプリングに対する6つの異なる設定条件下での固定予算設定において, \texttt{SHVV} の優れた性能を示す。 最後に,幾何学的ブラウン運動 (GBM) を用いて生成した100ドル株のコールオプション取引において, \texttt{UCB-VV} と \texttt{SHVV} の性能を実証的に評価するケーススタディを行う。

関連論文リスト

• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• Concurrent Learning with Aggregated States via Randomized Least Squares Value Iteration [40.73142019282658]
  ランダム化を注入することは、環境を連続的に探索するエージェントの社会に役立てるかどうかを考察する。 有限および無限水平環境における最悪の後悔境界を示す。 我々は空間の複雑さを$K$の係数で減らし、最悪ケースの後悔の上限を$sqrtK$だけ増やす。
  論文  参考訳（メタデータ） (2025-01-23T05:37:33Z)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
  論文  参考訳（メタデータ） (2023-07-25T15:42:11Z)
• Combinatorial Bandits for Maximum Value Reward Function under Max Value-Index Feedback [9.771002043127728]
  本稿では,最大値報酬関数に対する最大値と指数フィードバックに基づくマルチアームバンディット問題を考察する。 有限なサポートを持つ任意の分布にしたがって、アーム結果を持つ問題インスタンスに対して、アルゴリズムを提案し、後悔の束縛を与える。 我々のアルゴリズムは、$O(((k/Delta)log(T))$ distribution-dependent と $tildeO(sqrtT)$ distribution-independent regret を達成する。
  論文  参考訳（メタデータ） (2023-05-25T14:02:12Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。 トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
  論文  参考訳（メタデータ） (2023-03-30T02:51:00Z)
• Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds [34.37963000493442]
  本稿では,マルチアーム・バンディット(MAB)問題について考察し,両対向的条件下でほぼ最適に機能する,新たなベスト・オブ・ボス・ワールド(BOBW)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-14T12:58:46Z)
• Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
  我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。 学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。 コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
  論文  参考訳（メタデータ） (2021-06-18T15:01:01Z)
• Combinatorial Bandits without Total Order for Arms [52.93972547896022]
  セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。 我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
  論文  参考訳（メタデータ） (2021-03-03T23:08:59Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)

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

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