論文の概要: Rotting Infinitely Many-armed Bandits
- arxiv url: http://arxiv.org/abs/2201.12975v3
- Date: Sun, 17 Dec 2023 10:16:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-19 21:42:48.132582
- Title: Rotting Infinitely Many-armed Bandits
- Title（参考訳）: 無限に多くの腕のバンディットを腐らせる
- Authors: Jung-hun Kim, Milan Vojnovic, Se-Young Yun
- Abstract要約: 我々は$Omega(maxvarrho2/3T,sqrtT)$ worst-case regret lower bound ここで$T$は地平線時間であることを示す。
適応 UCB インデックスと適応しきい値を用いて $varrho$ の値を知らないアルゴリズムを実現することができる。
- 参考スコア（独自算出の注目度）: 33.26370721280417
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the infinitely many-armed bandit problem with rotting rewards,
where the mean reward of an arm decreases at each pull of the arm according to
an arbitrary trend with maximum rotting rate $\varrho=o(1)$. We show that this
learning problem has an $\Omega(\max\{\varrho^{1/3}T,\sqrt{T}\})$ worst-case
regret lower bound where $T$ is the horizon time. We show that a matching upper
bound $\tilde{O}(\max\{\varrho^{1/3}T,\sqrt{T}\})$, up to a poly-logarithmic
factor, can be achieved by an algorithm that uses a UCB index for each arm and
a threshold value to decide whether to continue pulling an arm or remove the
arm from further consideration, when the algorithm knows the value of the
maximum rotting rate $\varrho$. We also show that an
$\tilde{O}(\max\{\varrho^{1/3}T,T^{3/4}\})$ regret upper bound can be achieved
by an algorithm that does not know the value of $\varrho$, by using an adaptive
UCB index along with an adaptive threshold value.
- Abstract（参考訳）: 我々は,最大ロッティングレート$\varrho=o(1)$ の任意の傾向に従って腕の平均報酬が減少する,ロッティング報酬を伴う無限多腕バンディット問題を考える。
この学習問題には$\omega(\max\{\varrho^{1/3}t,\sqrt{t}\})$の最悪の場合の後悔の上限があり、ここで$t$は地平線時間である。
多対数係数の最大値まで一致する上限$\tilde{o}(\max\{\varrho^{1/3}t,\sqrt{t}\})$は、各腕に対してucbインデックスとしきい値を使って、最大回転率$\varrho$の値を知っているアルゴリズムが、腕を引っ張り続けるか、腕を外すかを判断するアルゴリズムによって達成できることを示す。
また、適応的 UCB 指数と適応的しきい値を用いて、$\tilde{O}(\max\{\varrho^{1/3}T,T^{3/4}\})$ regret upper bound が $\varrho$ の値を知らないアルゴリズムによって達成可能であることを示す。
関連論文リスト
- Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。
ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
論文 参考訳（メタデータ） (2024-04-02T12:15:37Z) - 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) - Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。
ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。
我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文 参考訳（メタデータ） (2023-02-07T02:22:31Z) - Non-stationary Bandits and Meta-Learning with a Small Set of Optimal
Arms [30.024167992890916]
そこで本研究では,学習者が200ドル(約1万2000円)の帯域幅のタスクに直面する決定について検討する。
敵は各タスクの最適なアームを、M$アームのより小さな(しかし未知の)サブセットで選択することを制約される。
境界は既知のもの(非定常的メタラーニング設定)、あるいは未知のもの(非定常的バンディット設定)である。
論文 参考訳（メタデータ） (2022-02-25T22:28:01Z) - Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delays [21.94728545221709]
制限のないフィードバック遅延を伴うMAB(Scale-Free Adversarial Multi Armed Bandit)問題を考える。
textttSFBankerは$mathcal O(sqrtK(D+T)L)cdot rm polylog(T, L)$ total regret, where $T$ is the total number of steps, $D$ is the total feedback delay。
論文 参考訳（メタデータ） (2021-10-26T04:06:51Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - 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) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳（メタデータ） (2021-02-15T19:10:52Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。