論文の概要: Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits

• arxiv url: http://arxiv.org/abs/2306.14872v3
• Date: Sat, 30 Dec 2023 20:16:23 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-03 02:07:54.276122
• Title: Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits
• Title（参考訳）: 線形バンドイットの性能と理論的保証のバランスをとる幾何アウェアアプローチ
• Authors: Yuwei Luo, Mohsen Bayati
• Abstract要約: トンプソンサンプリングとグリーディは有望な経験的性能を示したが、これは悲観的な理論的後悔の境界とは対照的である。 本研究では不確実楕円体の幾何学的特性を追跡する新しいデータ駆動手法を提案する。 ベースアルゴリズムが不十分な問題インスタンスを特定し,コース修正する。
• 参考スコア（独自算出の注目度）: 6.907555940790131
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper is motivated by recent research in the $d$-dimensional stochastic linear bandit literature, which has revealed an unsettling discrepancy: algorithms like Thompson sampling and Greedy demonstrate promising empirical performance, yet this contrasts with their pessimistic theoretical regret bounds. The challenge arises from the fact that while these algorithms may perform poorly in certain problem instances, they generally excel in typical instances. To address this, we propose a new data-driven technique that tracks the geometric properties of the uncertainty ellipsoid around the main problem parameter. This methodology enables us to formulate an instance-dependent frequentist regret bound, which incorporates the geometric information, for a broad class of base algorithms, including Greedy, OFUL, and Thompson sampling. This result allows us to identify and ``course-correct" problem instances in which the base algorithms perform poorly. The course-corrected algorithms achieve the minimax optimal regret of order $\tilde{\mathcal{O}}(d\sqrt{T})$ for a $T$-period decision-making scenario, effectively maintaining the desirable attributes of the base algorithms, including their empirical efficacy. We present simulation results to validate our findings using synthetic and real data.
• Abstract（参考訳）: 本論文は,d$-dimensional stochastic linear bandit literature(d$-dimensional stochastic linear bandit literature)における最近の研究の動機である。 この課題は、これらのアルゴリズムが特定の問題インスタンスではうまく機能しないが、典型例では優れているという事実から生じる。 そこで本研究では,問題パラメータ周辺の不確かさ楕円の幾何学的性質を追跡する新しいデータ駆動手法を提案する。 この手法により,Greedy,OFUL,Thompson サンプリングを含む幅広いアルゴリズムに対して,幾何情報を含むインスタンス依存の頻繁な後悔境界を定式化することができる。 この結果、ベースアルゴリズムが性能が悪い問題インスタンスを識別して ``course-correct" することができる。 コース修正アルゴリズムは、$T$周期決定シナリオに対して$\tilde{\mathcal{O}}(d\sqrt{T})$のミニマックス最適後悔を達成し、その経験的有効性を含む基本アルゴリズムの望ましい属性を効果的に維持する。 シミュレーションの結果を合成データと実データを用いて検証する。

関連論文リスト

• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。 提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
  論文  参考訳（メタデータ） (2024-10-22T10:19:27Z)
• Integer Programming for Learning Directed Acyclic Graphs from Non-identifiable Gaussian Models [6.54203362045253]
  本研究では,連続観測データから有向非巡回グラフを学習する問題について検討する。 中規模の問題を学習するための混合整数プログラミングフレームワークを開発した。 提案手法は最先端のアルゴリズムより優れ,ノイズの不均一性に対して頑健である。
  論文  参考訳（メタデータ） (2024-04-19T02:42:13Z)
• Towards Practical Robustness Auditing for Linear Regression [8.9598796481325]
  データセットの小さなサブセットの存在を発見または否定するアルゴリズムについて検討する。 これらの手法は, 技術の状況を大きく上回り, 数次元における回帰問題の堅牢性チェックに有用であることを示す。 我々は、アルゴリズムの頑健な統計学における最近の革新から引き出されたアイデアを用いて、スペクトルアルゴリズムを用いて、この課題を先導する。
  論文  参考訳（メタデータ） (2023-07-30T20:47:36Z)
• High-dimensional Contextual Bandit Problem without Sparsity [8.782204980889077]
  本稿では,この問題に対処し,その性能を検証するための探索列コミット(EtC)アルゴリズムを提案する。 我々は、ETCアルゴリズムの最適レートを$T$で導出し、探索とエクスプロイトのバランスをとることで、このレートを実現できることを示す。 本稿では,最適バランスを適応的に求める適応探索定理 (AEtC) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-19T15:29:32Z)
• Instance-Dependent Confidence and Early Stopping for Reinforcement Learning [99.57168572237421]
  強化学習(RL)のための様々なアルゴリズムは、その収束率の劇的な変動を問題構造の関数として示している。 この研究は、観察されたパフォーマンスの違いについて、textitexを説明する保証を提供する。 次の自然なステップは、これらの理論的保証を実際に有用なガイドラインに変換することです。
  論文  参考訳（メタデータ） (2022-01-21T04:25:35Z)
• Sparse PCA: Algorithms, Adversarial Perturbations and Certificates [9.348107805982604]
  標準統計モデルにおけるスパースPCAの効率的なアルゴリズムについて検討する。 私たちのゴールは、小さな摂動に耐性を持ちながら、最適な回復保証を達成することです。
  論文  参考訳（メタデータ） (2020-11-12T18:58:51Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。 マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
  論文  参考訳（メタデータ） (2020-03-06T16:17:24Z)

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

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