論文の概要: Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits

• arxiv url: http://arxiv.org/abs/2110.08057v1
• Date: Fri, 15 Oct 2021 12:32:33 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-18 14:48:50.819247
• Title: Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits
• Title（参考訳）: バッチ線形帯域に対するほぼ最適バッチ-回帰トレードオフ
• Authors: Zihan Zhang, Xiangyang Ji, Yuan Zhou
• Abstract要約: バッチ線形文脈帯域に対する最適バッチ-regretトレードオフについて検討する。 時間的地平線が成長するにつれて2相表現を特徴とする後悔の保証を証明します。 また, 動的上界に依存した新しい行列不等式濃度を証明した。
• 参考スコア（独自算出の注目度）: 45.43968161616453
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the optimal batch-regret tradeoff for batch linear contextual bandits. For any batch number $M$, number of actions $K$, time horizon $T$, and dimension $d$, we provide an algorithm and prove its regret guarantee, which, due to technical reasons, features a two-phase expression as the time horizon $T$ grows. We also prove a lower bound theorem that surprisingly shows the optimality of our two-phase regret upper bound (up to logarithmic factors) in the \emph{full range} of the problem parameters, therefore establishing the exact batch-regret tradeoff. Compared to the recent work \citep{ruan2020linear} which showed that $M = O(\log \log T)$ batches suffice to achieve the asymptotically minimax-optimal regret without the batch constraints, our algorithm is simpler and easier for practical implementation. Furthermore, our algorithm achieves the optimal regret for all $T \geq d$, while \citep{ruan2020linear} requires that $T$ greater than an unrealistically large polynomial of $d$. Along our analysis, we also prove a new matrix concentration inequality with dependence on their dynamic upper bounds, which, to the best of our knowledge, is the first of its kind in literature and maybe of independent interest.
• Abstract（参考訳）: バッチ線形文脈帯域に対する最適バッチ-回帰トレードオフについて検討する。 任意のバッチ番号$M$、アクションの数$K$、タイムホライズ$T$、ディメンション$d$に対して、アルゴリズムを提供し、その後悔の保証を証明する。 また、問題パラメータのemph{full range} における二相後悔の上界(対数因子まで)の最適性を示す下界定理を証明し、そのため正確なバッチ-レグレットトレードオフを確立した。 m = o(\log \log t)$ batches suffice がバッチ制約なしで漸近的に最適化された後悔を達成することを示す最近の研究である \citep{ruan2020linear} と比較すると、アルゴリズムはよりシンプルで実用的な実装が容易である。 さらに、我々のアルゴリズムは全ての$T \geq d$に対して最適の後悔を達成する一方、 \citep{ruan2020linear} は$T$が$d$の非現実的に大きい多項式よりも大きいことを要求する。 また, 動的上界に依存した新しい行列濃度不等式を証明し, 最善の知識として, 文学における最初のものとなり, 恐らく独立した興味を持つものと考えられる。

関連論文リスト

• Optimal Batched Linear Bandits [9.795531604467406]
  本稿では,探索・推定・探索の枠組みを取り入れたバッチ線形バンドイト問題に対するE$4$アルゴリズムを提案する。 探索速度の適切な選択により、E$4$は、$O(loglog T)$バッチのみで有限時間ミニマックス最適後悔を達成する。 探索レートの別の選択で、E$4$は、少なくとも$O(log T)$バッチを必要とするインスタンス依存の後悔境界を達成することを示す。
  論文  参考訳（メタデータ） (2024-06-06T14:57:52Z)
• 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)
• Parameter-free Regret in High Probability with Heavy Tails [45.11667443216861]
  非有界領域に対するオンライン凸最適化のための新しいアルゴリズムを提案する。 高確率のパラメータフリーな後悔は、潜在的に重み付き下次推定にのみアクセス可能である。
  論文  参考訳（メタデータ） (2022-10-25T21:43:44Z)
• Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
  我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。 我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2022-03-29T15:27:13Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Bandit [10.604939762790517]
  我々は、累積後悔に対して、$mathcalObig((log d)fracalpha+12Tfrac1-alpha2+log Tbig)$をミニマックス下界として証明する。 第2に,汎用的なアッパー信頼境界(UCB)戦略に着想を得た,シンプルで効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-23T19:35:38Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
  論文  参考訳（メタデータ） (2020-10-22T19:14:37Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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