論文の概要: Context-lumpable stochastic bandits

• arxiv url: http://arxiv.org/abs/2306.13053v1
• Date: Thu, 22 Jun 2023 17:20:30 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-23 13:25:23.301344
• Title: Context-lumpable stochastic bandits
• Title（参考訳）: コンテキスト結合型確率的包帯
• Authors: Chung-Wei Lee, Qinghua Liu, Yasin Abbasi-Yadkori, Chi Jin, Tor Lattimore, Csaba Szepesv\'ari
• Abstract要約: 我々は、$S $コンテキストと$A $アクションのコンテキスト的バンディット問題を考える。 まず,PAC設定における準最適サンプルの複雑さと,この問題に対するオンライン設定において,$widetilde O(sqrtpoly(r)(S+K)T)$ minimaxの後悔を示す。
• 参考スコア（独自算出の注目度）: 55.77691166697947
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider a contextual bandit problem with $S $ contexts and $A $ actions. In each round $t=1,2,\dots$ the learner observes a random context and chooses an action based on its past experience. The learner then observes a random reward whose mean is a function of the context and the action for the round. Under the assumption that the contexts can be lumped into $r\le \min\{S ,A \}$ groups such that the mean reward for the various actions is the same for any two contexts that are in the same group, we give an algorithm that outputs an $\epsilon$-optimal policy after using at most $\widetilde O(r (S +A )/\epsilon^2)$ samples with high probability and provide a matching $\widetilde\Omega(r (S +A )/\epsilon^2)$ lower bound. In the regret minimization setting, we give an algorithm whose cumulative regret up to time $T$ is bounded by $\widetilde O(\sqrt{r^3(S +A )T})$. To the best of our knowledge, we are the first to show the near-optimal sample complexity in the PAC setting and $\widetilde O(\sqrt{{poly}(r)(S+K)T})$ minimax regret in the online setting for this problem. We also show our algorithms can be applied to more general low-rank bandits and get improved regret bounds in some scenarios.
• Abstract（参考訳）: 我々は、$S $コンテキストと$A $アクションのコンテキスト的バンディット問題を考える。 各ラウンド$t=1,2,\dots$ では、学習者はランダムな文脈を観察し、過去の経験に基づいてアクションを選択する。 そして、学習者は、平均が文脈の関数であり、ラウンドに対するアクションであるランダムな報酬を観察する。 コンテキストを$r\le \min\{s ,a \}$ グループにまとめることができて、同じグループに属する2つのコンテキストに対して平均報酬が同じであると仮定すると、最大$\widetilde o(r (s +a )/\epsilon^2)$ のサンプルを高い確率で使用して、$\widetilde\omega(r (s +a )/\epsilon^2)$ の値と一致する$\widetilde\omega(r (s +a )/\epsilon^2)$ の値を求めるアルゴリズムを与える。 後悔の最小化設定では、T$までの累積後悔を$\widetilde O(\sqrt{r^3(S +A )T})$で束縛するアルゴリズムを与える。 我々の知る限り、我々はPAC設定におけるほぼ最適サンプルの複雑さを初めて示し、この問題のオンライン設定において、$\widetilde O(\sqrt{{poly}(r)(S+K)T})$ minimax regret を示す。 また、我々のアルゴリズムはより一般的な低ランクバンディットに適用でき、いくつかのシナリオで改善された後悔境界が得られることを示す。

関連論文リスト

• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
  本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。 政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。 提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
  論文  参考訳（メタデータ） (2024-02-24T06:36:08Z)
• 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)
• Instance-optimal PAC Algorithms for Contextual Bandits [20.176752818200438]
  この作業では、$(epsilon,delta)$-$textitPAC$設定における帯域幅の問題に焦点を当てます。 最良腕識別のための最小限の後悔最小化とインスタンス依存のPACを同時に行うアルゴリズムは存在しないことを示す。
  論文  参考訳（メタデータ） (2022-07-05T23:19:43Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• On Submodular Contextual Bandits [92.45432756301231]
  作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
  論文  参考訳（メタデータ） (2021-12-03T21:42:33Z)
• 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)

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

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