論文の概要: 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$への依存を取り除くアプローチは、独立した関心事かもしれない。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - First- and Second-Order Bounds for Adversarial Linear Contextual Bandits [22.367921675238318]
我々は,K$の腕に付随する損失関数を制限なく時間とともに変化させることができる,逆線形文脈帯域設定を考える。
V_T$ または $L_T*$ は$T$ よりもかなり小さい可能性があるため、環境が比較的良心的であれば、最悪の場合の後悔よりも改善される。
論文 参考訳(メタデータ) (2023-05-01T14:00:15Z) - Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。
我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文 参考訳(メタデータ) (2023-03-15T17:59:27Z) - Contextual Bandits with Packing and Covering Constraints: A Modular
Lagrangian Approach via Regression [99.27350939441146]
我々は,線形制約付きコンテキスト帯域(CBwLC)を,knapsacks(CBwK)を用いたコンテキスト帯域(CBwLC)の変種として検討する。
この問題はknapsackでコンテキストの帯域幅を一般化し、制約のパッケージ化とカバー、そして正と負のリソース消費を可能にする。
回帰オラクルに基づくCBwLC(CBwK)の最初のアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-11-14T16:08:44Z) - Double Doubly Robust Thompson Sampling for Generalized Linear Contextual
Bandits [8.508198765617198]
一般化線形報酬に$tildeO(sqrtkappa-1 phi T)$ regret over $T$ roundsを提案する。
また、確率的マージン条件下では、$O(kappa-1 phi log (NT) log T)$ regret bound for $N$ arms も提供する。
論文 参考訳(メタデータ) (2022-09-15T00:20:38Z) - The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret
and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。
一般関数クラスと一般モデルクラスで学ぶことに集中する。
対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文 参考訳(メタデータ) (2022-03-03T02:55:55Z) - Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits [45.43968161616453]
バッチ線形文脈帯域に対する最適バッチ-regretトレードオフについて検討する。
時間的地平線が成長するにつれて2相表現を特徴とする後悔の保証を証明します。
また, 動的上界に依存した新しい行列不等式濃度を証明した。
論文 参考訳(メタデータ) (2021-10-15T12:32:33Z) - Provably Efficient Reinforcement Learning with Linear Function
Approximation Under Adaptivity Constraints [94.76881135901753]
一般的な限定的適応モデルとして,バッチ学習モデルとレアポリシースイッチモデルがある。
提案したLSVI-UCB-Batchアルゴリズムは,$tilde O(sqrtd3H3T + dHT/B)$ regretを実現する。
まれなポリシスイッチモデルでは,提案されたLSVI-UCB-RareSwitchアルゴリズムは,$tilde O(sqrtd3H3T[1+T/(dH)]dH/B)$の後悔を享受する。
論文 参考訳(メタデータ) (2021-01-06T18:56:07Z) - Linear Bandits with Limited Adaptivity and Learning Distributional
Optimal Design [12.465883735626605]
オンライン能動学習の中心的課題である線形文脈帯域に対する適応性制約の影響について検討する。
文脈ベクトルが$d$次元線形文脈包帯で逆選択された場合、学習者はミニマックス最適後悔を達成するために$O(d log d log T)$ポリシースイッチが必要であることを示す。
論文 参考訳(メタデータ) (2020-07-04T01:34:22Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。