論文の概要: Online Learning with Knapsacks: the Best of Both Worlds

• arxiv url: http://arxiv.org/abs/2202.13710v1
• Date: Mon, 28 Feb 2022 12:10:48 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-01 17:21:26.286747
• Title: Online Learning with Knapsacks: the Best of Both Worlds
• Title（参考訳）: Knapsacksによるオンライン学習 - 両方の世界のベスト
• Authors: Matteo Castiglioni, Andrea Celli, Christian Kroer
• Abstract要約: オンライン学習の課題として,意思決定者が,リソース制約の有限セットに違反することなく,期待する報酬を最大化したい,という課題を提起する。 当社のフレームワークは,意思決定者がそのエビデンスを柔軟かつコスト論的に扱えるようにします。
• 参考スコア（独自算出の注目度）: 54.28273783164608
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study online learning problems in which a decision maker wants to maximize their expected reward without violating a finite set of $m$ resource constraints. By casting the learning process over a suitably defined space of strategy mixtures, we recover strong duality on a Lagrangian relaxation of the underlying optimization problem, even for general settings with non-convex reward and resource-consumption functions. Then, we provide the first best-of-both-worlds type framework for this setting, with no-regret guarantees both under stochastic and adversarial inputs. Our framework yields the same regret guarantees of prior work in the stochastic case. On the other hand, when budgets grow at least linearly in the time horizon, it allows us to provide a constant competitive ratio in the adversarial case, which improves over the $O(m \log T)$ competitive ratio of Immorlica at al. (2019). Moreover, our framework allows the decision maker to handle non-convex reward and cost functions. We provide two game-theoretic applications of our framework to give further evidence of its flexibility.
• Abstract（参考訳）: 意思決定者は,リソース制約の有限セットに違反することなく,期待する報酬を最大化しようとするオンライン学習問題を考察する。 戦略混合の適切な定義空間上に学習プロセスをキャストすることで、非凸報酬と資源消費関数を持つ一般的な設定であっても、基礎となる最適化問題のラグランジュ緩和において強い双対性を回復する。 そして,この設定に対して,確率的および対角的入力の両方で保証されない,初めてのベスト・オブ・ワールド型フレームワークを提供する。 我々の枠組みは、確率的な場合の先行作業に対する同じ後悔の保証をもたらす。 一方、予算が少なくとも時間軸で線形に増加すると、逆の場合には一定の競争比率が与えられ、al. (2019) におけるimmorlica の$o(m \log t)$ の競争比率が向上する。 さらに、このフレームワークにより、意思決定者が非凸報酬やコスト関数を処理できる。 このフレームワークの2つのゲーム理論的な応用を提供し、柔軟性のさらなる証拠を与えます。

関連論文リスト

• Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
  後悔は$Thetaleft(mfrac12cdotfrac11-2-Tright)$で半直線的に成長するので、指数関数的に$Theta(sqrtm)$に収束する。 これらの調査結果は、限定的なオンライン学習と最適化の利点を浮き彫りにしている。
  論文  参考訳（メタデータ） (2024-06-20T23:00:25Z)
• Beyond Expectations: Learning with Stochastic Dominance Made Practical [88.06211893690964]
  支配は、不確実な結果で意思決定を行うためのリスク-逆の選好をモデル化する。 理論上は魅力的だが、機械学習における優位性の応用は乏しい。 まず支配の概念を一般化し、任意の確率変数の任意のペア間の比較を可能にする。 次に、優位性の観点から最適解を見つけるための単純で効率的なアプローチを開発する。
  論文  参考訳（メタデータ） (2024-02-05T03:21:23Z)
• Bandits with Replenishable Knapsacks: the Best of both Worlds [26.786438972889208]
  非単調な資源利用を可能にするBwKフレームワークの自然な一般化について検討する。 入力モデルの下で、我々のアルゴリズムはインスタンスに依存しない $tildeO(T1/2)$ regret bound を生成する。
  論文  参考訳（メタデータ） (2023-06-14T12:34:00Z)
• Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
  制約付きオンライン学習問題に対する既存の原始双対アルゴリズムは、2つの基本的な仮定に依存している。 このような仮定は、標準の原始双対テンプレートを弱適応的後悔最小化器で与えることによって、どのように回避できるのかを示す。 上記の2つの前提が満たされていない場合に保証される、世界の最高の保証を証明します。
  論文  参考訳（メタデータ） (2023-02-02T16:30:33Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Stochastic Compositional Optimization with Compositional Constraints [8.535822787583486]
  単一レベルの期待値と2レベルの構成制約を現在のSCOフレームワークに組み込んだ新しいモデルについて検討する。 我々のモデルは、リスク-逆最適化やハイモーメントポートフォリオの選択など、データ駆動最適化やリスク管理に広く適用することができる。 本稿では, 最適解に収束するシーケンスを, 単レベル期待値と2レベル構成制約の両方で$cO(frac1sqrtN)$underで生成するアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2022-09-09T02:06:35Z)
• Best of Both Worlds Model Selection [39.211071446838474]
  ネストされた政策クラスが存在する場合のバンディットシナリオにおけるモデル選択の問題について検討する。 私たちのアプローチでは、各ベース学習者は、保持するかもしれないし持たないかもしれない後悔の候補を伴わなければならない。 これらは、(線形)バンディットのシナリオでモデル選択を行いながら、(確率的および敵対的)双方の保証を最大限に達成する最初の理論的結果である。
  論文  参考訳（メタデータ） (2022-06-29T20:57:30Z)
• Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation [107.06364966905821]
  線形2次レギュレータ(LQR)設定における探索・探索ジレンマについて検討した。 有限 MDP に対する楽観的アルゴリズムで用いられる拡張値反復アルゴリズムに着想を得て,Oulq の楽観的最適化を緩和することを提案する。 我々は、少なくとも$Obig(log (1/epsilon)big)$ Riccati方程式を解くことで、$epsilon$-OptimisticControllerを効率的に計算できることを示した。
  論文  参考訳（メタデータ） (2020-07-13T16:30:47Z)

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

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