論文の概要: Optimal Regret with Limited Adaptivity for Generalized Linear Contextual Bandits

• arxiv url: http://arxiv.org/abs/2404.06831v1
• Date: Wed, 10 Apr 2024 08:47:57 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-11 15:10:01.498919
• Title: Optimal Regret with Limited Adaptivity for Generalized Linear Contextual Bandits
• Title（参考訳）: 一般化線形コンテキスト帯域に対する適応性に制限のある最適レグレット
• Authors: Ayush Sawarni, Nirjhar Das, Gaurav Sinha, Siddharth Barman,
• Abstract要約: 限定適応性の要求条件の中で、一般化線形文脈帯域問題について検討する。 我々は2つのアルゴリズム、textttB-GLinCB と textttRS-GLinCB を示し、それぞれ2つの限定適応モデルに対処する。
• 参考スコア（独自算出の注目度）: 12.112051468737596
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the generalized linear contextual bandit problem within the requirements of limited adaptivity. In this paper, we present two algorithms, \texttt{B-GLinCB} and \texttt{RS-GLinCB}, that address, respectively, two prevalent limited adaptivity models: batch learning with stochastic contexts and rare policy switches with adversarial contexts. For both these models, we establish essentially tight regret bounds. Notably, in the obtained bounds, we manage to eliminate a dependence on a key parameter $\kappa$, which captures the non-linearity of the underlying reward model. For our batch learning algorithm \texttt{B-GLinCB}, with $\Omega\left( \log{\log T} \right)$ batches, the regret scales as $\tilde{O}(\sqrt{T})$. Further, we establish that our rarely switching algorithm \texttt{RS-GLinCB} updates its policy at most $\tilde{O}(\log^2 T)$ times and achieves a regret of $\tilde{O}(\sqrt{T})$. Our approach for removing the dependence on $\kappa$ for generalized linear contextual bandits might be of independent interest.
• Abstract（参考訳）: 限定適応性の要求条件の中で、一般化線形文脈帯域問題について検討する。 本稿では,2つのアルゴリズム, \texttt{B-GLinCB} と \texttt{RS-GLinCB} について述べる。 これら2つのモデルに対して、基本的には厳密な後悔境界を確立する。 特に、得られたバウンダリにおいて、基礎となる報酬モデルの非線形性をキャプチャするキーパラメータ$\kappa$への依存を取り除くことに成功している。 バッチ学習アルゴリズム \texttt{B-GLinCB} の場合、$\Omega\left( \log{\log T} \right)$ バッチは $\tilde{O}(\sqrt{T})$ となる。 さらに、我々のめったに切り替えないアルゴリズム \texttt{RS-GLinCB} がそのポリシーを最大$\tilde{O}(\log^2T)$倍に更新し、$\tilde{O}(\sqrt{T})$を後悔する。 一般化された文脈的帯域に対する$\kappa$への依存を取り除くアプローチは、独立した関心事かもしれない。

関連論文リスト

• First- and Second-Order Bounds for Adversarial Linear Contextual Bandits [22.367921675238318]
  我々は,K$の腕に付随する損失関数を制限なく時間とともに変化させることができる,逆線形文脈帯域設定を考える。 V_T$ または $L_T*$ は$T$ よりもかなり小さい可能性があるため、環境が比較的良心的であれば、最悪の場合の後悔よりも改善される。
  論文  参考訳（メタデータ） (2023-05-01T14:00:15Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。 ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。 我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15:55:44Z)
• 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)
• Batched Bandits with Crowd Externalities [11.876737078654976]
  Batched Multi-Armed Bandits (BMAB) の新たな設定について述べる。 ポリシー更新のタイミングはBMABアルゴリズムによって制御されず、代わりに、textitcrowdと呼ばれる各バッチで受信されたデータの量は、過去のアームの選択に影響される。
  論文  参考訳（メタデータ） (2021-09-29T21:43:16Z)
• Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
  オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。 当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
  論文  参考訳（メタデータ） (2021-09-29T14:07:21Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。 経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
  論文  参考訳（メタデータ） (2021-03-25T18:52:17Z)
• Problem-Complexity Adaptive Model Selection for Stochastic Linear Bandits [20.207989166682832]
  2つの一般的な線形バンディット設定におけるモデル選択の問題について考察する。 まず、[K]$におけるarm $iの平均的な報酬は、$mu_i+ langle alpha_i,t,theta*|$である。 我々は、ALBが$O(|theta*|sqrtT)$の後悔のスケーリングを達成することを示す。
  論文  参考訳（メタデータ） (2020-06-04T02:19:00Z)

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

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