論文の概要: Regret Minimization via Saddle Point Optimization

• arxiv url: http://arxiv.org/abs/2403.10379v1
• Date: Fri, 15 Mar 2024 15:09:13 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-18 16:32:11.759328
• Title: Regret Minimization via Saddle Point Optimization
• Title（参考訳）: サドルポイント最適化によるレグレト最小化
• Authors: Johannes Kirschner, Seyed Alireza Bakhtiari, Kushagra Chandak, Volodymyr Tkachuk, Csaba Szepesvári,
• Abstract要約: 決定推定係数 (DEC) は, 構造的バンディットと強化学習における最悪の既往歴に対して, ほぼ下限および上限の値を与えることを示した。 推定・判定アルゴリズム(E2D)の任意の変種を導出する。 我々の定式化は有限モデルクラスと線形フィードバックモデルのための実用的なアルゴリズムにつながる。
• 参考スコア（独自算出の注目度）: 29.78262192683203
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A long line of works characterizes the sample complexity of regret minimization in sequential decision-making by min-max programs. In the corresponding saddle-point game, the min-player optimizes the sampling distribution against an adversarial max-player that chooses confusing models leading to large regret. The most recent instantiation of this idea is the decision-estimation coefficient (DEC), which was shown to provide nearly tight lower and upper bounds on the worst-case expected regret in structured bandits and reinforcement learning. By re-parametrizing the offset DEC with the confidence radius and solving the corresponding min-max program, we derive an anytime variant of the Estimation-To-Decisions (E2D) algorithm. Importantly, the algorithm optimizes the exploration-exploitation trade-off online instead of via the analysis. Our formulation leads to a practical algorithm for finite model classes and linear feedback models. We further point out connections to the information ratio, decoupling coefficient and PAC-DEC, and numerically evaluate the performance of E2D on simple examples.
• Abstract（参考訳）: 長い一連の研究は、min-maxプログラムによるシーケンシャルな意思決定における後悔の最小化のサンプルの複雑さを特徴づけている。 対応するサドルポイントゲームにおいて、ミニプレイヤは、大きな後悔につながる混乱モデルを選択する敵極大プレーヤに対してサンプリング分布を最適化する。 このアイデアの最も最近のインスタンス化は決定推定係数 (DEC) であり、これは構造的バンディットと強化学習における最悪のケースで予想される後悔に対して、ほぼ確実に下限と上限を提供することを示した。 オフセットDECを信頼半径で再パラメータ化し、対応するmin-maxプログラムを解くことにより、推定-to-Decisions(E2D)アルゴリズムの時変を導出する。 重要な点として、このアルゴリズムは、分析によってではなく、オンラインでの探索と探索のトレードオフを最適化する。 我々の定式化は有限モデルクラスと線形フィードバックモデルのための実用的なアルゴリズムにつながる。 さらに、情報比、疎結合係数、PAC-DECとの接続を指摘し、簡単な例でE2Dの性能を数値的に評価する。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。 これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-04-16T20:01:10Z)
• Constrained Online Two-stage Stochastic Optimization: Near Optimal Algorithms via Adversarial Learning [1.994307489466967]
  有限地平線上の長期制約付きオンライン2段階最適化をT$周期で検討する。 対戦型学習アルゴリズムからオンライン二段階問題のオンラインアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2023-02-02T10:33:09Z)
• Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments [48.96971760679639]
  マルコフ決定過程(MDP)の分散依存的後悔境界について検討する。 環境の微細な分散特性を特徴付けるための2つの新しい環境規範を提案する。 モデルに基づく手法では、MVPアルゴリズムの変種を設計する。 特に、この境界は極小かつ決定論的 MDP に対して同時に最適である。
  論文  参考訳（メタデータ） (2023-01-31T06:54:06Z)
• COCO Denoiser: Using Co-Coercivity for Variance Reduction in Stochastic Convex Optimization [4.970364068620608]
  我々は,勾配オラクルによって出力される雑音の推定値を改善するために,凸性およびL平滑性を利用する。 問合せ点の数と近さの増加は、より良い勾配推定に繋がることを示す。 また、SGD、Adam、STRSAGAといった既存のアルゴリズムにCOCOをプラグインすることで、バニラ設定にもCOCOを適用します。
  論文  参考訳（メタデータ） (2021-09-07T17:21:09Z)
• Adaptive Importance Sampling for Finite-Sum Optimization and Sampling with Decreasing Step-Sizes [4.355567556995855]
  ステップサイズを小さくした有限サム最適化とサンプリングのための適応的重要度サンプリングのための簡易かつ効率的なアルゴリズムであるavareを提案する。 標準的な技術的条件下では、$mathcalO(T2/3)$と$mathcalO(T5/6)$の動的後悔をそれぞれ、$mathcalO(T5/6)$のステップサイズで実行するときに達成している。
  論文  参考訳（メタデータ） (2021-03-23T00:28:15Z)
• Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
  我々は、最悪のケース分布を特徴付けるために神経生成モデルを使うことを議論する。 このアプローチは多くの実装と最適化の課題をもたらします。 提案されたアプローチは、同等のベースラインよりも堅牢なモデルを生み出す。
  論文  参考訳（メタデータ） (2021-03-18T14:26:26Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes [53.72166325215299]
  エピソード因子化マルコフ決定過程(FMDP)における最小強化学習について検討する。 第一に、分解された構造のリッチなクラスに対する最小限の後悔の保証を達成する。 2つ目は、少し悪い後悔をしながら、より良い計算複雑性を楽しみます。
  論文  参考訳（メタデータ） (2020-06-24T00:50:17Z)

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

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