論文の概要: Near-optimal Per-Action Regret Bounds for Sleeping Bandits

• arxiv url: http://arxiv.org/abs/2403.01315v2
• Date: Thu, 30 May 2024 00:18:21 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-31 20:54:36.745529
• Title: Near-optimal Per-Action Regret Bounds for Sleeping Bandits
• Title（参考訳）: 睡眠帯域に対する近接最適パーアクションレグレクト境界
• Authors: Quan Nguyen, Nishant A. Mehta,
• Abstract要約: 睡眠中の包帯に対して, 行動毎のほぼ最適な後悔境界を導出する。 合計で$K$、最大で$A$の武器が各ラウンドで$T$以上の場合、最もよく知られている上限は$O(KsqrtTAlnK)$である。 本研究は睡眠専門家のアドバイスで盗賊の設定まで拡張し,その過程でEXP4を一般化する。
• 参考スコア（独自算出の注目度）: 8.261117235807607
• 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$のサブ線形であるが、その活性ラウンドの数に線形な作用が存在することを示す。

関連論文リスト

• Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds [1.03590082373586]
  本稿では,線形帯域探索アルゴリズムTRAiLの提案と解析を行う。 TraiLは、設計(回帰器)行列の最小固有値によって測定された推論品質の$Omega(sqrtT)$成長を保証する。 我々は,期待された後悔に対して,任意のアルゴリズムに対して$Omega(sqrtT)$ minimax小境界を特徴付ける。
  論文  参考訳（メタデータ） (2024-11-19T01:08:13Z)
• Improved Regret Bounds for Bandits with Expert Advice [16.699381591572163]
  我々は、最悪のケースの後悔に対して$sqrtK T ln(N/K)$の下位境界を証明し、そこでは$K$はアクションの数、$N>K$はエキスパートの数、$T$はタイムホライズである。 これは、前述した同じ順序の上界と一致し、$sqrtK T (ln N) / (ln K)$の最良の下界を改善する。
  論文  参考訳（メタデータ） (2024-06-24T17:14:31Z)
• Adversarial Multi-dueling Bandits [0.4467766778351321]
  対戦型多段バンディットにおける後悔の問題について紹介する。 このような嗜好フィードバックから学習するための新しいアルゴリズム MiDEX (Multi Dueling EXP3) を導入する。
  論文  参考訳（メタデータ） (2024-06-18T10:28:12Z)
• Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
  本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。 ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
  論文  参考訳（メタデータ） (2024-04-02T12:15:37Z)
• 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)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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