論文の概要: Linear Bandits on Ellipsoids: Minimax Optimal Algorithms
- arxiv url: http://arxiv.org/abs/2502.17175v1
- Date: Mon, 24 Feb 2025 14:12:31 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-25 15:57:58.295299
- Title: Linear Bandits on Ellipsoids: Minimax Optimal Algorithms
- Title（参考訳）: 楕円体上の線形帯域:ミニマックス最適アルゴリズム
- Authors: Raymond Zhang, Hedi Hadiji, Richard Combes,
- Abstract要約: 作用の集合が楕円体であるような計算線形帯域を考える。
この問題に対して、最初の既知のミニマックス最適アルゴリズムを提供する。
実行には、時間$O(dT + d2 log(T/d) + d3)$とメモリ$O(d2)$のみが必要である。
- 参考スコア（独自算出の注目度）: 5.678465386088928
- License:
- Abstract: We consider linear stochastic bandits where the set of actions is an ellipsoid. We provide the first known minimax optimal algorithm for this problem. We first derive a novel information-theoretic lower bound on the regret of any algorithm, which must be at least $\Omega(\min(d \sigma \sqrt{T} + d \|\theta\|_{A}, \|\theta\|_{A} T))$ where $d$ is the dimension, $T$ the time horizon, $\sigma^2$ the noise variance, $A$ a matrix defining the set of actions and $\theta$ the vector of unknown parameters. We then provide an algorithm whose regret matches this bound to a multiplicative universal constant. The algorithm is non-classical in the sense that it is not optimistic, and it is not a sampling algorithm. The main idea is to combine a novel sequential procedure to estimate $\|\theta\|$, followed by an explore-and-commit strategy informed by this estimate. The algorithm is highly computationally efficient, and a run requires only time $O(dT + d^2 \log(T/d) + d^3)$ and memory $O(d^2)$, in contrast with known optimistic algorithms, which are not implementable in polynomial time. We go beyond minimax optimality and show that our algorithm is locally asymptotically minimax optimal, a much stronger notion of optimality. We further provide numerical experiments to illustrate our theoretical findings.
- Abstract（参考訳）: 作用の集合が楕円体である線形確率的包帯を考える。
この問題に対して、最初の既知のミニマックス最適アルゴリズムを提供する。
まず、任意のアルゴリズムの後悔に関する新しい情報理論の下界を導出し、少なくとも$\Omega(\min(d \sigma \sqrt{T} + d \|\theta\|_{A}, \|\theta\|_{A} T))$$$d$は次元、$T$は時間軸、$\sigma^2$はノイズ分散、$A$はアクションの集合を定義する行列、$\theta$は未知パラメータのベクトルである。
次に、これを乗法的普遍定数に限定した後悔のアルゴリズムを提供する。
アルゴリズムは楽観的ではなく、サンプリングアルゴリズムではないという意味では古典的ではない。
第一の考え方は、$\|\theta\|$を推定するための新しいシーケンシャルな手順を組み合わせることであり、続いてこの推定から得られる探索とコミットの戦略が続く。
このアルゴリズムは計算効率が高く、実行には時間$O(dT + d^2 \log(T/d) + d^3)$とメモリ$O(d^2)$が必要である。
我々はミニマックス最適性を超えて、我々のアルゴリズムは局所的に漸近的にミニマックス最適であり、より強力な最適性の概念であることを示す。
さらに,我々の理論的知見を説明するための数値実験を行った。
関連論文リスト
- Achieving Tractable Minimax Optimal Regret in Average Reward MDPs [19.663336027878408]
我々は,$widetildemathrmO(sqrtmathrmsp(h*) S A T)$のミニマックス最適後悔を伴う最初の抽出可能なアルゴリズムを提案する。
注目すべきは、我々のアルゴリズムは$mathrmsp(h*)$に関する事前情報を必要としないことである。
論文 参考訳（メタデータ） (2024-06-03T11:53:44Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed
Rewards [40.99322897009357]
トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。
我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。
我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
論文 参考訳（メタデータ） (2023-10-28T13:01:10Z) - Optimal Exploration is no harder than Thompson Sampling [14.726673043806391]
a pure exploration linear bandit problem to return $argmax_zin mathcalZ ztoptheta_ast with $xtoptheta_ast with $xin mathcalXsubset mathbbRd$。
この複雑さは、後続サンプリングとargmaxオラクルへのアクセスを必要とするだけであり、$mathcalZ$を列挙する必要がない、後悔の最小化のために人気で単純なトンプソンサンプリングと矛盾する。
論文 参考訳（メタデータ） (2023-10-09T18:21:39Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
論文 参考訳（メタデータ） (2021-12-21T01:54:17Z) - 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) - Classical algorithms and quantum limitations for maximum cut on
high-girth graphs [6.262125516926276]
すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。
1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
論文 参考訳（メタデータ） (2021-06-10T16:28:23Z) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-09T05:39:05Z) - Randomized Exploration is Near-Optimal for Tabular MDP [45.16374124699648]
強化学習におけるThompson Sampling(TS)ライクアルゴリズムにおけるランダム化値関数を用いた探索について検討する。
1)1つのランダムシードを各エピソードで使用し、2)ベルンシュタイン型のノイズの大きさを算出すると、最悪の$widetildeOleft(HsqrtSATright)$リコールがエピソード時間非均質決定プロセスにバインドされることを示します。
論文 参考訳（メタデータ） (2021-02-19T01:42:50Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。