論文の概要: Truncated LinUCB for Stochastic Linear Bandits

• arxiv url: http://arxiv.org/abs/2202.11735v1
• Date: Wed, 23 Feb 2022 19:01:27 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-26 09:40:05.266033
• Title: Truncated LinUCB for Stochastic Linear Bandits
• Title（参考訳）: 確率線形帯域に対するTruncated LinUCB
• Authors: Yanglei Song, Meng zhou
• Abstract要約: LinUCBアルゴリズムは、関連する線形帯域に最適に近い最小値である。 LinUCBのtruncatedバージョンが提案され、Tr-LinUCBと呼ばれている。
• 参考スコア（独自算出の注目度）: 7.696636937455892
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper considers contextual bandits with a finite number of arms, where the contexts are independent and identically distributed $d$-dimensional random vectors, and the expected rewards are linear in both the arm parameters and contexts. The LinUCB algorithm, which is near minimax optimal for related linear bandits, is shown to have a cumulative regret that is suboptimal in both the dimension $d$ and time horizon $T$, due to its over-exploration. A truncated version of LinUCB is proposed and termed "Tr-LinUCB", which follows LinUCB up to a truncation time $S$ and performs pure exploitation afterwards. The Tr-LinUCB algorithm is shown to achieve $O(d\log(T))$ regret if $S = Cd\log(T)$ for a sufficiently large constant $C$, and a matching lower bound is established, which shows the rate optimality of Tr-LinUCB in both $d$ and $T$ under a low dimensional regime. Further, if $S = d\log^{\kappa}(T)$ for some $\kappa>1$, the loss compared to the optimal is a multiplicative $\log\log(T)$ factor, which does not depend on $d$. This insensitivity to overshooting in choosing the truncation time of Tr-LinUCB is of practical importance.
• Abstract（参考訳）: 本稿では,コンテキストが独立で分散された$d$次元ランダムベクトルであり,armパラメータとコンテキストの両方において期待される報酬が線形であるような,有限個のアームを持つコンテキストバンディットを考察する。 LinUCBアルゴリズムは、関連する線形包帯に対して最小値に近いが、その過剰探索のため、次元$d$と時間地平線$T$の両方で最適である累積的後悔を持つことが示されている。 LinUCB のtruncated バージョンが提案され "Tr-LinUCB" と呼ばれ、LinUCB は truncation time $S$ まで続く。 Tr-LinUCBアルゴリズムは、十分に大きな定数である$C$に対して$S = Cd\log(T)$が$O(d\log(T))$後悔し、一致する下限を確立し、低次元の条件下では$d$と$T$の両方でTr-LinUCBの速度最適性を示す。 さらに、ある$\kappa>1$に対して$S = d\log^{\kappa}(T)$であれば、最適値に対する損失は乗法的な$\log\log(T)$ factorであり、$d$に依存しない。 Tr-LinUCBの切断時間を選択する際のオーバーシューティングに対する感度は、実用上重要である。

関連論文リスト

• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。 UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。 我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
  論文  参考訳（メタデータ） (2024-05-24T04:11:58Z)
• 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)
• First- and Second-Order Bounds for Adversarial Linear Contextual Bandits [22.367921675238318]
  我々は,K$の腕に付随する損失関数を制限なく時間とともに変化させることができる,逆線形文脈帯域設定を考える。 V_T$ または $L_T*$ は$T$ よりもかなり小さい可能性があるため、環境が比較的良心的であれば、最悪の場合の後悔よりも改善される。
  論文  参考訳（メタデータ） (2023-05-01T14:00:15Z)
• On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Bandits [76.2262680277608]
  本研究では,線形関数クラスによって期待される報酬関数を近似できるような,不特定条件下での線形文脈帯域について検討する。 このアルゴリズムは, 対数的因子に比例した設定において, ギャップ依存の残差が$tilde O (d2/Delta)$と同じであることを示す。
  論文  参考訳（メタデータ） (2023-03-16T15:24:29Z)
• Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits [45.43968161616453]
  バッチ線形文脈帯域に対する最適バッチ-regretトレードオフについて検討する。 時間的地平線が成長するにつれて2相表現を特徴とする後悔の保証を証明します。 また, 動的上界に依存した新しい行列不等式濃度を証明した。
  論文  参考訳（メタデータ） (2021-10-15T12:32:33Z)
• An Efficient Pessimistic-Optimistic Algorithm for Constrained Linear Bandits [16.103685478563072]
  本稿では,一般制約付き線形帯域について考察する。 目的は、各ラウンドにおける一連の制約の対象となる水平線上の累積報酬を最大化することである。 本稿では,この問題に対する悲観的最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-10T07:30:37Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes [91.38793800392108]
  本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。 上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。 我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
  論文  参考訳（メタデータ） (2020-12-15T18:56:46Z)
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation [99.59319332864129]
  最近提案された2つの線形MDP仮定で対数的後悔が達成可能であることを示す。 我々の知る限り、これらは線型関数近似を持つRLに対する最初の対数的後悔境界である。
  論文  参考訳（メタデータ） (2020-11-23T17:25:00Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)

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

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