論文の概要: Best-of-Both-Worlds Algorithms for Linear Contextual Bandits
- arxiv url: http://arxiv.org/abs/2312.15433v2
- Date: Mon, 19 Feb 2024 13:46:18 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-21 03:57:12.621188
- Title: Best-of-Both-Worlds Algorithms for Linear Contextual Bandits
- Title（参考訳）: 線形コンテキスト帯域に対するBest-of-Both-Worldsアルゴリズム
- Authors: Yuko Kuroki, Alberto Rumi, Taira Tsuchiya, Fabio Vitale, Nicol\`o
Cesa-Bianchi
- Abstract要約: 両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
- 参考スコア（独自算出の注目度）: 11.94312915280916
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study best-of-both-worlds algorithms for $K$-armed linear contextual
bandits. Our algorithms deliver near-optimal regret bounds in both the
adversarial and stochastic regimes, without prior knowledge about the
environment. In the stochastic regime, we achieve the polylogarithmic rate
$\frac{(dK)^2\mathrm{poly}\log(dKT)}{\Delta_{\min}}$, where $\Delta_{\min}$ is
the minimum suboptimality gap over the $d$-dimensional context space. In the
adversarial regime, we obtain either the first-order
$\widetilde{O}(dK\sqrt{L^*})$ bound, or the second-order
$\widetilde{O}(dK\sqrt{\Lambda^*})$ bound, where $L^*$ is the cumulative loss
of the best action and $\Lambda^*$ is a notion of the cumulative second moment
for the losses incurred by the algorithm. Moreover, we develop an algorithm
based on FTRL with Shannon entropy regularizer that does not require the
knowledge of the inverse of the covariance matrix, and achieves a
polylogarithmic regret in the stochastic regime while obtaining
$\widetilde{O}\big(dK\sqrt{T}\big)$ regret bounds in the adversarial regime.
- Abstract（参考訳）: 両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、環境に関する事前の知識なしに、敵対的かつ確率的な体制において、ほぼ最適の後悔境界を提供する。
確率的状態において、多元対数率 $\frac{(dK)^2\mathrm{poly}\log(dKT)}{\Delta_{\min}}$, ここで、$\Delta_{\min}$ は$d$次元の文脈空間上の最小部分最適化ギャップである。
逆系では、一階の $\widetilde{O}(dK\sqrt{L^*})$bound または二階の $\widetilde{O}(dK\sqrt{\Lambda^*})$bound を得る。
さらに, 共分散行列の逆の知識を必要としないシャノンエントロピー正規化器を用いたFTRLに基づくアルゴリズムを開発し, 確率的状態における多対数的後悔を実現するとともに, 逆数的状態において$\widetilde{O}\big(dK\sqrt{T}\big)$ regret boundsを得る。
関連論文リスト
- LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits [38.41164102066483]
本研究では、独立かつ同一に分散したコンテキストを持つ線形文脈帯域問題について考察する。
提案アルゴリズムは、Tsallisエントロピーを持つFollow-The-Regularized-Leaderに基づいており、$alpha$-textual-Con (LC)-Tsallis-INFと呼ばれている。
論文 参考訳（メタデータ） (2024-03-05T18:59:47Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - Best-of-Both-Worlds Linear Contextual Bandits [45.378265414553226]
本研究は, 対向汚職下での多武装盗賊問題の事例である$K$腕線形文脈盗賊の問題を考察する。
我々は,理論的保証のもと,双方の敵環境に有効な戦略を開発する。
両体制の理論的保証から,我々の戦略をBest-of-Both-Worlds (BoBW) RealFTRLと呼んでいる。
論文 参考訳（メタデータ） (2023-12-27T09:32:18Z) - Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback [30.337826346496385]
線形マルコフ決定過程におけるオンライン強化学習について,敵対的損失と帯域幅フィードバックを用いて検討した。
既存の手法と比較して、後悔性能を向上させるアルゴリズムを2つ導入する。
論文 参考訳（メタデータ） (2023-10-17T19:43:37Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Computationally Efficient Horizon-Free Reinforcement Learning for Linear
Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。
我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。
これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文 参考訳（メタデータ） (2022-05-23T17:59:18Z) - 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) - An Algorithm for Stochastic and Adversarial Bandits with Switching Costs [10.549307055348596]
そこで本研究では,マルチアームバンディットのスイッチングコストを考慮したアルゴリズムを提案し,そのアルゴリズムがアームを切り替える度に$lambda$を支払う。
私たちのアルゴリズムは、Zimmert and Seldin(2021)のTsallis-INFアルゴリズムの適応に基づいています。
論文 参考訳（メタデータ） (2021-02-19T11:03:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。