論文の概要: Linear bandits with polylogarithmic minimax regret
- arxiv url: http://arxiv.org/abs/2402.12042v1
- Date: Mon, 19 Feb 2024 10:56:47 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-20 17:05:41.651811
- Title: Linear bandits with polylogarithmic minimax regret
- Title（参考訳）: 多対数ミニマックス後悔を伴うリニアバンディット
- Authors: Josep Lumbreras, Marco Tomamichel
- Abstract要約: 本研究では,未知ベクトルに近づいた単位球上での動作を選択すると,サブガウス雑音パラメータが線形に消滅する線形帯域の雑音モデルについて検討する。
我々は,この問題に対するアルゴリズムを導入し,この最小限の後悔のスケーリングを,時間軸で$log3(T)$,時間軸で$T$として示す。
- 参考スコア（独自算出の注目度）: 10.60608983034705
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study a noise model for linear stochastic bandits for which the
subgaussian noise parameter vanishes linearly as we select actions on the unit
sphere closer and closer to the unknown vector. We introduce an algorithm for
this problem that exhibits a minimax regret scaling as $\log^3(T)$ in the time
horizon $T$, in stark contrast the square root scaling of this regret for
typical bandit algorithms. Our strategy, based on weighted least-squares
estimation, achieves the eigenvalue relation $\lambda_{\min} ( V_t ) = \Omega
(\sqrt{\lambda_{\max}(V_t ) })$ for the design matrix $V_t$ at each time step
$t$ through geometrical arguments that are independent of the noise model and
might be of independent interest. This allows us to tightly control the
expected regret in each time step to be of the order $O(\frac1{t})$, leading to
the logarithmic scaling of the cumulative regret.
- Abstract（参考訳）: 本研究では,未知ベクトルに近い単位球面上の動作を選択することで,サブガウス雑音パラメータが線形に消失する線形確率バンディットの雑音モデルについて検討する。
従来のバンディットアルゴリズムに対する後悔の正方根スケーリングとは対照的に、この問題のアルゴリズムは、time horizon $t$において、minimax regret scalingを$\log^3(t)$として示す。
我々の戦略は、重み付き最小二乗推定に基づいて、ノイズモデルとは独立で独立した幾何学的議論を通じて、設計行列 $v_t$ に対して、固有値関係 $\lambda_{\min} ( v_t ) = \omega (\sqrt{\lambda_{\max}(v_t ) }) を達成する。
これにより、各時間ステップにおける期待された後悔を$O(\frac1{t})$の順番で厳格に制御することができ、累積的後悔の対数的スケーリングにつながる。
関連論文リスト
- Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds [1.03590082373586]
本稿では,線形帯域探索アルゴリズムTRAiLの提案と解析を行う。
TraiLは、設計(回帰器)行列の最小固有値によって測定された推論品質の$Omega(sqrtT)$成長を保証する。
我々は,期待された後悔に対して,任意のアルゴリズムに対して$Omega(sqrtT)$ minimax小境界を特徴付ける。
論文 参考訳（メタデータ） (2024-11-19T01:08:13Z) - Improved Bound for Robust Causal Bandits with Linear Models [16.60875994745622]
本稿では,時間的モデル変動に直面した因果包帯のロバスト性について検討する。
提案アルゴリズムは,$C$が$o(sqrtT)$の場合に,ほぼ最適な$tildemathcalO(sqrtT)$後悔を達成する。
論文 参考訳（メタデータ） (2024-05-13T14:41:28Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。
我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文 参考訳（メタデータ） (2023-03-15T17:59:27Z) - Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。
より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。
我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
論文 参考訳（メタデータ） (2023-03-05T15:11:14Z) - Exploration in Linear Bandits with Rich Action Sets and its Implications
for Inference [23.364534479492715]
期待行列の最小固有値は、アルゴリズムの累積後悔が$sqrtn)$であるときに、$Omega(sqrtn)として増加することを示す。
本研究は, 線形帯域におけるEmphmodel selectionとEmphclusteringの2つの実践シナリオに適用する。
論文 参考訳（メタデータ） (2022-07-23T20:25:07Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。