論文の概要: Near-optimal Per-Action Regret Bounds for Sleeping Bandits
- arxiv url: http://arxiv.org/abs/2403.01315v1
- Date: Sat, 2 Mar 2024 21:22:46 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-05 14:20:03.088231
- Title: Near-optimal Per-Action Regret Bounds for Sleeping Bandits
- Title(参考訳): 睡眠帯域に対する近接最適パーアクションレグレクト境界
- Authors: Quan Nguyen, Nishant A. Mehta
- Abstract要約: 睡眠中の包帯に対して, 行動毎のほぼ最適な後悔境界を導出する。
合計で$K$、最大で$A$の武器が各ラウンドで$T$以上の場合、最もよく知られている上限は$O(KsqrtTAlnK)$である。
本研究は睡眠専門家のアドバイスで盗賊の設定まで拡張し,その過程でEXP4を一般化する。
- 参考スコア(独自算出の注目度): 9.759415650727894
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We derive near-optimal per-action regret bounds for sleeping bandits, in
which both the sets of available arms and their losses in every round are
chosen by an adversary. In a setting with $K$ total arms and at most $A$
available arms in each round over $T$ rounds, the best known upper bound is
$O(K\sqrt{TA\ln{K}})$, obtained indirectly via minimizing internal sleeping
regrets. Compared to the minimax $\Omega(\sqrt{TA})$ lower bound, this upper
bound contains an extra multiplicative factor of $K\ln{K}$. We address this gap
by directly minimizing the per-action regret using generalized versions of
EXP3, EXP3-IX and FTRL with Tsallis entropy, thereby obtaining near-optimal
bounds of order $O(\sqrt{TA\ln{K}})$ and $O(\sqrt{T\sqrt{AK}})$. We extend our
results to the setting of bandits with advice from sleeping experts,
generalizing EXP4 along the way. This leads to new proofs for a number of
existing adaptive and tracking regret bounds for standard non-sleeping bandits.
Extending our results to the bandit version of experts that report their
confidences leads to new bounds for the confidence regret that depends
primarily on the sum of experts' confidences. We prove a lower bound, showing
that for any minimax optimal algorithms, there exists an action whose regret is
sublinear in $T$ but linear in the number of its active rounds.
- Abstract(参考訳): 我々は、利用可能な腕のセットと各ラウンドの損失の両方が敵によって選択される睡眠用バンディットに対して、最適に近い行動毎の後悔の限界を導出する。
合計で$K$、各ラウンドで$A$の武器が$T$以上の場合、最もよく知られている上限は$O(K\sqrt{TA\ln{K}})$で、内部の睡眠不足を最小化することで間接的に得られる。
ミニマックス $\Omega(\sqrt{TA})$ 下界と比較して、この上界は$K\ln{K}$の余剰乗算因子を含む。
このギャップは EXP3, EXP3-IX および FTRL の一般化版を Tsallis entropy を用いて直接最小化し、従って位数 $O(\sqrt{TA\ln{K}})$ と $O(\sqrt{T\sqrt{AK}})$ の準最適境界を得る。
本研究は睡眠専門家のアドバイスで盗賊の設定まで拡張し,その過程でEXP4を一般化する。
これは、標準的な非スリーピング帯域に対する多くの既存の適応的および追跡的後悔境界に対する新しい証明につながる。
彼らの自信を報告する専門家の活気あるバージョンに結果を拡張することは、主に専門家の自信の総和に依存する信頼の後悔に対する新たな限界をもたらす。
我々は、任意のミニマックス最適アルゴリズムに対して、後悔が$T$のサブ線形であるが、その活性ラウンドの数に線形な作用が存在することを示す。
関連論文リスト
- First- and Second-Order Bounds for Adversarial Linear Contextual Bandits [22.367921675238318]
我々は,K$の腕に付随する損失関数を制限なく時間とともに変化させることができる,逆線形文脈帯域設定を考える。
V_T$ または $L_T*$ は$T$ よりもかなり小さい可能性があるため、環境が比較的良心的であれば、最悪の場合の後悔よりも改善される。
論文 参考訳(メタデータ) (2023-05-01T14:00:15Z) - 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) - Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。
我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
論文 参考訳(メタデータ) (2022-03-29T15:27:13Z) - 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) - Impact of Representation Learning in Linear Bandits [83.17684841392754]
本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。
我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-10-13T16:35:30Z) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳(メタデータ) (2020-08-10T08:30:52Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-17T22:32:19Z) - Explicit Best Arm Identification in Linear Bandits Using No-Regret
Learners [17.224805430291177]
線形パラメータ化マルチアームバンドにおけるベストアーム識別の問題について検討する。
そこで本研究では,この問題を解決するために,明示的に実装可能かつ証明可能な順序-最適サンプル-複雑度アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-13T05:00:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。