論文の概要: Generalized Linear Bandits with Limited Adaptivity

• arxiv url: http://arxiv.org/abs/2404.06831v3
• Date: Fri, 14 Jun 2024 08:11:11 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-17 18:42:49.658033
• Title: Generalized Linear Bandits with Limited Adaptivity
• Title（参考訳）: 適応性に制限のある一般化線形帯域
• Authors: Ayush Sawarni, Nirjhar Das, Siddharth Barman, Gaurav Sinha,
• Abstract要約: 限定適応性の制約内における一般化線形文脈帯域問題について検討する。 我々は2つのアルゴリズム, $textttB-GLinCB$ と $textttRS-GLinCB$ を提示した。
• 参考スコア（独自算出の注目度）: 12.112051468737596
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We study the generalized linear contextual bandit problem within the constraints of limited adaptivity. In this paper, we present two algorithms, $\texttt{B-GLinCB}$ and $\texttt{RS-GLinCB}$, that address, respectively, two prevalent limited adaptivity settings. Given a budget $M$ on the number of policy updates, in the first setting, the algorithm needs to decide upfront $M$ rounds at which it will update its policy, while in the second setting it can adaptively perform $M$ policy updates during its course. For the first setting, we design an algorithm $\texttt{B-GLinCB}$, that incurs $\tilde{O}(\sqrt{T})$ regret when $M = \Omega\left( \log{\log T} \right)$ and the arm feature vectors are generated stochastically. For the second setting, we design an algorithm $\texttt{RS-GLinCB}$ that updates its policy $\tilde{O}(\log^2 T)$ times and achieves a regret of $\tilde{O}(\sqrt{T})$ even when the arm feature vectors are adversarially generated. Notably, in these bounds, we manage to eliminate the dependence on a key instance dependent parameter $\kappa$, that captures non-linearity of the underlying reward model. Our novel approach for removing this dependence for generalized linear contextual bandits might be of independent interest.
• Abstract（参考訳）: 限定適応性の制約内における一般化線形文脈帯域問題について検討する。 本稿では,2つのアルゴリズム, $\textt{B-GLinCB}$ と $\textt{RS-GLinCB}$ を示す。 最初の設定では、ポリシー更新の件数でM$が支払われると、アルゴリズムは、ポリシーを更新するラウンドを前もってM$が決定され、2つ目の設定では、コース中にM$が適応的にポリシー更新される。 最初の設定では、$M = \Omega\left( \log{\log T} \right)$と腕の特徴ベクトルが確率的に生成されるときに、$\tilde{O}(\sqrt{T})$後悔を引き起こすアルゴリズムを設計する。 2つ目の設定では、アルゴリズム $\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)

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

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