論文の概要: Bandits with many optimal arms
- arxiv url: http://arxiv.org/abs/2103.12452v1
- Date: Tue, 23 Mar 2021 11:02:31 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-24 22:11:17.572372
- Title: Bandits with many optimal arms
- Title（参考訳）: 多くの最適な腕を持つバンディット
- Authors: Rianne de Heide and James Cheshire and Pierre M\'enard and Alexandra
Carpentier
- Abstract要約: 最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
- 参考スコア（独自算出の注目度）: 68.17472536610859
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider a stochastic bandit problem with a possibly infinite number of
arms. We write $p^*$ for the proportion of optimal arms and $\Delta$ for the
minimal mean-gap between optimal and sub-optimal arms. We characterize the
optimal learning rates both in the cumulative regret setting, and in the
best-arm identification setting in terms of the problem parameters $T$ (the
budget), $p^*$ and $\Delta$. For the objective of minimizing the cumulative
regret, we provide a lower bound of order $\Omega(\log(T)/(p^*\Delta))$ and a
UCB-style algorithm with matching upper bound up to a factor of
$\log(1/\Delta)$. Our algorithm needs $p^*$ to calibrate its parameters, and we
prove that this knowledge is necessary, since adapting to $p^*$ in this setting
is impossible. For best-arm identification we also provide a lower bound of
order $\Omega(\exp(-cT\Delta^2p^*))$ on the probability of outputting a
sub-optimal arm where $c>0$ is an absolute constant. We also provide an
elimination algorithm with an upper bound matching the lower bound up to a
factor of order $\log(1/\Delta)$ in the exponential, and that does not need
$p^*$ or $\Delta$ as parameter.
- Abstract（参考訳）: 我々は、おそらく無限の腕を持つ確率的バンディット問題を考える。
最適アームの比率は$p^*$ であり、最適アームと準最適アームの間の最小平均ガップは$\delta$ である。
我々は、累積的な後悔の設定と、問題のパラメータである$t$(予算)、$p^*$、$\delta$という観点で、最適学習率を特徴付ける。
累積的後悔を最小限に抑えるため、位数$\Omega(\log(T)/(p^*\Delta))$と、上限値が$\log(1/\Delta)$に一致するUPBスタイルのアルゴリズムを提供する。
我々のアルゴリズムはパラメータを校正するために$p^*$を必要とし、この設定で$p^*$に適応することは不可能であるため、この知識が必要であることを証明します。
最良アームの識別には、$c>0$ が絶対定数である部分最適アームを出力する確率について、$\omega(\exp(-ct\delta^2p^*))$ という順序の下限も与える。
また、指数関数において下界が$\log(1/\Delta)$の係数に一致する上限を持つ除去アルゴリズムを提供し、パラメータとして$p^*$や$\Delta$を必要としない。
関連論文リスト
- A/B Testing and Best-arm Identification for Linear Bandits with
Robustness to Non-stationarity [28.068960555415014]
非定常環境下での線形包帯の固定予算ベストアーム識別問題について検討する。
アルゴリズムは、可能な限り高い確率で最適な腕 $x* := argmax_xinmathcalXxtopsum_t=1Ttheta_t$ を正しく識別することを目的としている。
論文 参考訳（メタデータ） (2023-07-27T19:03:36Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - On the complexity of All $\varepsilon$-Best Arms Identification [2.1485350418225244]
ガウスの報酬を持つ有限の多腕バンディットにおいて、$varepsilon$-optimal armsを全て識別する問題を考える。
我々は,$varepsilon$-good arms w.h.p の集合を同定し,期待されるサンプルの複雑さの観点から最適性($delta$が 0 になるとき)を享受するトラック・アンド・ストップアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-13T10:54:52Z) - Differentially Private Multi-Armed Bandits in the Shuffle Model [58.22098764071924]
シャッフルモデルにおけるマルチアームバンディット(MAB)問題に対して,$(varepsilon,delta)$-differentially privateアルゴリズムを提案する。
我々の上限は、集中モデルにおいて最もよく知られたアルゴリズムの後悔とほぼ一致し、局所モデルにおいて最もよく知られたアルゴリズムを著しく上回っている。
論文 参考訳（メタデータ） (2021-06-05T14:11:01Z) - Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
連続的なスイッチング制約を伴うオンライン凸最適化の問題を紹介する。
強い凸関数の場合、後悔境界は$O(log T)$ for $S=Omega(log T)$、$O(minT/exp(S)+S,T)$ for $S=O(log T)$に改善できることを示す。
論文 参考訳（メタデータ） (2021-03-21T11:43:35Z) - Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment [7.4288915613206505]
本研究では,バンディットとフルインフォメーションの両方のフィードバックの下で,オンライン学習環境における個人差分問題について検討する。
差分的な私的盗賊に対しては、UTBとトンプソンサンプリングに基づくアルゴリズムを同時に提案し、最適な$O左(sum_j: Delta_j>0 fracln(T)min leftDelta_j, epsilon right)$ minimax lower boundとする。
同じ差分プライベートなフル情報設定に対しては、$epsilon$-differentially も提示する。
論文 参考訳（メタデータ） (2021-02-16T02:48:16Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - 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) - Optimal $\delta$-Correct Best-Arm Selection for Heavy-Tailed
Distributions [2.2940141855172036]
我々は、$delta$-correctアルゴリズムを用いて、最大平均値を持つものを識別する問題を考察する。
$delta$-correctアルゴリズムの下位境界はよく知られている。
我々は,下界の$delta$-correctアルゴリズムを提案し,$delta$を0に還元する。
論文 参考訳（メタデータ） (2019-08-24T05:31:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。