論文の概要: Instance-Optimality in Interactive Decision Making: Toward a Non-Asymptotic Theory

• arxiv url: http://arxiv.org/abs/2304.12466v1
• Date: Mon, 24 Apr 2023 21:51:58 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-26 22:36:58.148070
• Title: Instance-Optimality in Interactive Decision Making: Toward a Non-Asymptotic Theory
• Title（参考訳）: 対話的意思決定におけるインスタンス最適性:非漸近理論に向けて
• Authors: Andrew Wagenmaker, Dylan J. Foster
• Abstract要約: 適応性の強い概念であるインスタンス最適化を目指しており、どの問題の場合であっても、検討中のアルゴリズムは全ての一貫したアルゴリズムより優れていると主張する。 本稿では,一般関数近似を用いたインスタンス最適決定の非漸近的理論の開発に向けて第一歩を踏み出す。
• 参考スコア（独自算出の注目度）: 30.061707627742766
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the development of adaptive, instance-dependent algorithms for interactive decision making (bandits, reinforcement learning, and beyond) that, rather than only performing well in the worst case, adapt to favorable properties of real-world instances for improved performance. We aim for instance-optimality, a strong notion of adaptivity which asserts that, on any particular problem instance, the algorithm under consideration outperforms all consistent algorithms. Instance-optimality enjoys a rich asymptotic theory originating from the work of \citet{lai1985asymptotically,graves1997asymptotically}, but non-asymptotic guarantees have remained elusive outside of certain special cases. Even for problems as simple as tabular reinforcement learning, existing algorithms do not attain instance-optimal performance until the number of rounds of interaction is doubly exponential in the number of states. In this paper, we take the first step toward developing a non-asymptotic theory of instance-optimal decision making with general function approximation. We introduce a new complexity measure, the Allocation-Estimation Coefficient (AEC), and provide a new algorithm, $\mathsf{AE}^2$, which attains non-asymptotic instance-optimal performance at a rate controlled by the AEC. Our results recover the best known guarantees for well-studied problems such as finite-armed and linear bandits and, when specialized to tabular reinforcement learning, attain the first instance-optimal regret bounds with polynomial dependence on all problem parameters, improving over prior work exponentially. We complement these results with lower bounds that show that i) existing notions of statistical complexity are insufficient to derive non-asymptotic guarantees, and ii) under certain technical conditions, boundedness of the AEC is necessary to learn an instance-optimal allocation of decisions in finite time.
• Abstract（参考訳）: 我々は,対話型意思決定(帯域,強化学習など)のための適応型インスタンス依存アルゴリズムの開発を検討する。 適応性の強い概念であるインスタンス最適化を目指しており、どの問題の場合であっても、検討中のアルゴリズムは全ての一貫したアルゴリズムより優れていると主張する。 インスタンス最適性は \citet{lai 1985asymptotically,graves1997asymptotically} の業績に由来する豊富な漸近理論を享受するが、非漸近的保証は特定の特別な場合以外でも解明されていない。 テーブル型強化学習のような単純な問題であっても、既存のアルゴリズムは、インタラクションのラウンド数が2倍に指数関数的になるまでインスタンス最適化性能を達成できない。 本稿では,一般関数近似を用いてインスタンス最適決定の非漸近理論を開発するための第一歩を踏み出す。 本稿では,新しい複雑性尺度である割り当て推定係数(aec)を導入し,aecが制御するレートで非漸近的なインスタンス最適性能を実現する新しいアルゴリズムである$\mathsf{ae}^2$を提案する。 本結果は,有限武器や線形包帯などのよく研究されている問題に対する保証を回復し,表型強化学習に特化すれば,全ての問題パラメータに対する多項式依存による最初のインスタンス最適後悔境界を達成でき,先行作業よりも指数関数的に改善される。 これらの結果を下限で補うことで 一 統計複雑性の既存の概念は、非漸近的保証を導出することができないこと、及び 二 特定の技術的条件の下では、AECの有界性は、有限時間以内に、決定のインスタンス最適配分を学習するために必要である。

関連論文リスト

• Asymptotic and Non-Asymptotic Convergence of AdaGrad for Non-Convex Optimization via Novel Stopping Time-based Analysis [17.34603953600226]
  我々はAdaの革新的な包括的分析を導入し、文献の既存のギャップを埋める。 AdaGradの期待は、ほぼ確実に、平均的にもたらされます。 また,既存の結果と無関係に予測された平均非a-bpt-d勾配を実証した。
  論文  参考訳（メタデータ） (2024-09-08T08:29:51Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。 我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。 提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
  論文  参考訳（メタデータ） (2022-11-14T21:54:31Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Non-asymptotic estimates for TUSLA algorithm for non-convex learning with applications to neural networks with ReLU activation function [3.5044892799305956]
  Lovas et alで導入された未調整Langevinアルゴリズム(TUSLA)の非漸近解析を行う。 特に、Wassersteinstein-1-2におけるTUSLAアルゴリズムの非漸近誤差境界を確立する。 TUSLAアルゴリズムは最適解に急速に収束することを示す。
  論文  参考訳（メタデータ） (2021-07-19T07:13:02Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。 提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
  論文  参考訳（メタデータ） (2020-06-08T09:25:47Z)
• Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
  我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。 我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
  論文  参考訳（メタデータ） (2020-03-16T17:15:28Z)

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

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