Fugu-MT 論文翻訳(概要): A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret

論文の概要: A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret

arxiv url: http://arxiv.org/abs/2609.05895v1
Date: Sat, 05 Sep 2026 05:30:29 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-10 19:44:08.163869
Title: A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret
Title（参考訳）: 規則付きオンライン資源配分のための一次学習アルゴリズム
Abstract要約: 地平線に比例した初期資源容量を有する有限水平オンライン資源割り当て問題について検討する。本稿では、各期間に、現在の要求タイプに関連するアクション座標の勾配上昇更新を行う、一次一階述語学習ポリシーを提案する。
参考スコア（独自算出の注目度）: 6.929167893040819
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study a finite-horizon online resource allocation problem with initial resource capacities proportional to the horizon. In each period, a request type is observed and one action is chosen from a finite menu. Each action earns a reward and consumes a vector of resources. The arrival types are independent and identically distributed, but their probabilities are unknown. We present a primal first-order learning policy that, in each period, performs one gradient ascent update of the action coordinates associated with the current request type. The policy achieves $O(1)$ expected additive regret relative to the hindsight optimum, with a bound independent of the horizon $T$. It does not solve any linear program, and the regret bound does not require a nondegeneracy assumption on the fluid linear program.
Abstract（参考訳）: 地平線に比例した初期資源容量を有する有限水平オンライン資源割り当て問題について検討する。各期間でリクエストタイプが観察され、有限メニューから1つのアクションが選択される。各アクションは報酬を受け取り、リソースのベクターを消費する。到着型は独立であり、同じ分布であるが、その確率は不詳である。本稿では、各期間に、現在の要求タイプに関連するアクション座標の勾配上昇更新を行う、一次一階述語学習ポリシーを提案する。このポリシーは、後続の最適値に対して$O(1)$期待加法的後悔を達成し、水平線の独立性は$T$である。線形プログラムを解くことはなく、遺言境界は流体線形プログラムに非退化的仮定を必要としない。

関連論文リスト

A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming [29.531157410826825]
非定常オンライン線形計画法(OLP)について検討する。 OLPでは、$n$の注文は、独立だが必ずしも同一に分散されたランダムベクトルの列を形成する報酬と資源の消費のペアと共に順次届く。本稿では,動的プログラミングの観点を,従来の静止環境において採用されていたデュアルベースフレームワークと統合した新しい再解法を提案する。
論文参考訳（メタデータ） (2026-03-15T23:59:30Z)
Non-Stationary Online Resource Allocation: Learning from a Single Sample [5.81028169940199]
最低限のオフラインデータ要求で,非定常要求下でのオンラインリソース割り当てについて検討する。本稿では,この問題をモジュラーコンポーネントに分解する,型依存型量子型メタ政治を提案する。
論文参考訳（メタデータ） (2026-02-20T10:07:35Z)
No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need! [56.80767500991973]
アクション選択の前に報酬とコストが観測される$(i)$オンラインリソース割当と、アクション選択後、完全なフィードバックや盗賊フィードバックの下で、リソース制限付きオンライン学習である$(ii)$オンラインリソース割当に焦点を当てた。報酬とコスト分布が時間とともに任意に変化する場合、これらの設定でサブ線形後悔を達成することは不可能であることが知られている。我々は、支出計画に従う基準線に対する半線形後悔を実現する一般的な(基本的)二重的手法を設計し、また、支出計画が予算のバランスの取れた配分を保証すると、アルゴリズムの性能が向上する。
論文参考訳（メタデータ） (2025-06-16T08:42:31Z)
Online Resource Allocation in Episodic Markov Decision Processes [1.8416014644193066]
本稿では, 有限水平制約マルコフ決定過程におけるオンライン割当問題として, 問題を定式化する。本稿では,観測・観測・観測・観測体制の整備と既存の決定・観測体制の改善について述べる。平均報酬と平均資源消費関数にアクセスできる静的最適政策に対する後悔は、高い確率で$tilde O(rho-1H3/2SsqrtAT)$で束縛されていることを示す。
論文参考訳（メタデータ） (2023-05-18T06:28:34Z)
Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
論文参考訳（メタデータ） (2023-03-17T17:53:28Z)
No-regret Algorithms for Fair Resource Allocation [18.955298050888736]
制限のない敵に対する非制約設定において、公平な資源配分問題を考える。この問題は$alpha$-fairness関数の非加法性のため難しい。オンライン・プロポーショナル・フェア(OPF)と呼ばれる,効率的なオンライン資源配分政策を提案する。
論文参考訳（メタデータ） (2023-03-11T12:15:19Z)
Online Allocation with Two-sided Resource Constraints [44.5635910908944]
我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-12-28T02:21:06Z)
Reinforcement Learning in Reward-Mixing MDPs [74.41782017817808]
報酬混合マルコフ決定過程(MDP)におけるエピソード強化学習 cdot S2 A2)$ episodes, where$H$ is time-horizon and $S, A$ are the number of state and actions。 epsilon$-optimal policy after $tildeO(poly(H,epsilon-1) cdot S2 A2)$ episodes, $H$ is time-horizon and $S, A$ are the number of state and actions。
論文参考訳（メタデータ） (2021-10-07T18:55:49Z)
Coordinated Online Learning for Multi-Agent Systems with Coupled Constraints and Perturbed Utility Observations [91.02019381927236]
本研究では, 資源制約を満たすため, エージェントを安定な集団状態へ誘導する新しい手法を提案する。提案手法は,ゲームラグランジアンの拡張によるリソース負荷に基づく分散リソース価格設定手法である。
論文参考訳（メタデータ） (2020-10-21T10:11:17Z)
Policy Gradient for Continuing Tasks in Non-stationary Markov Decision Processes [112.38662246621969]
強化学習は、マルコフ決定プロセスにおいて期待される累積報酬を最大化するポリシーを見つけることの問題を考える。我々は、ポリシーを更新するために上昇方向として使用する値関数の偏りのないナビゲーション勾配を計算する。ポリシー勾配型アルゴリズムの大きな欠点は、定常性の仮定が課せられない限り、それらがエピソジックなタスクに限定されていることである。
論文参考訳（メタデータ） (2020-10-16T15:15:42Z)
Hierarchical Adaptive Contextual Bandits for Resource Constraint based Recommendation [49.69139684065241]
コンテキスト多重武装バンディット(MAB)は、様々な問題において最先端のパフォーマンスを達成する。本稿では,階層型適応型文脈帯域幅法(HATCH)を提案する。
論文参考訳（メタデータ） (2020-04-02T17:04:52Z)

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