論文の概要: No-regret Algorithms for Fair Resource Allocation
- arxiv url: http://arxiv.org/abs/2303.06396v1
- Date: Sat, 11 Mar 2023 12:15:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-14 19:09:24.031776
- Title: No-regret Algorithms for Fair Resource Allocation
- Title（参考訳）: 公平な資源配分のための非回帰アルゴリズム
- Authors: Abhishek Sinha, Ativ Joshi, Rajarshi Bhattacharjee, Cameron Musco,
Mohammad Hajiesmaili
- Abstract要約: 制限のない敵に対する非制約設定において、公平な資源配分問題を考える。
この問題は$alpha$-fairness関数の非加法性のため難しい。
オンライン・プロポーショナル・フェア(OPF)と呼ばれる,効率的なオンライン資源配分政策を提案する。
- 参考スコア（独自算出の注目度）: 18.955298050888736
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We consider a fair resource allocation problem in the no-regret setting
against an unrestricted adversary. The objective is to allocate resources
equitably among several agents in an online fashion so that the difference of
the aggregate $\alpha$-fair utilities of the agents between an optimal static
clairvoyant allocation and that of the online policy grows sub-linearly with
time. The problem is challenging due to the non-additive nature of the
$\alpha$-fairness function. Previously, it was shown that no online policy can
exist for this problem with a sublinear standard regret. In this paper, we
propose an efficient online resource allocation policy, called Online
Proportional Fair (OPF), that achieves $c_\alpha$-approximate sublinear regret
with the approximation factor $c_\alpha=(1-\alpha)^{-(1-\alpha)}\leq 1.445,$
for $0\leq \alpha < 1$. The upper bound to the $c_\alpha$-regret for this
problem exhibits a surprising phase transition phenomenon. The regret bound
changes from a power-law to a constant at the critical exponent
$\alpha=\frac{1}{2}.$ As a corollary, our result also resolves an open problem
raised by Even-Dar et al. [2009] on designing an efficient no-regret policy for
the online job scheduling problem in certain parameter regimes. The proof of
our results introduces new algorithmic and analytical techniques, including
greedy estimation of the future gradients for non-additive global reward
functions and bootstrapping adaptive regret bounds, which may be of independent
interest.
- Abstract（参考訳）: 制限のない敵に対する無規制設定における公平な資源配分問題を考える。
目的は、エージェントの$\alpha$-fairユーティリティの最適な静的透視的割り当てとオンラインポリシーの割り当ての差が時間とともに非線形に増加するように、オンラインの方法で複数のエージェント間で公平にリソースを割り当てることである。
この問題は、$\alpha$-fairness関数の非加法性のために難しい。
従来、この問題に対するオンラインポリシーは存在せず、サブリニア標準の後悔は生じなかった。
本稿では,オンライン比例フェア (opf) と呼ばれる効率的なオンライン資源配分ポリシーを提案し,近似係数 $c_\alpha=(1-\alpha)^{-(1-\alpha)}\leq 1.445,$0\leq \alpha < 1$ で$c_\alpha$-approximate sublinear regret を実現する。
この問題に対する$c_\alpha$-regret の上限は驚くべき相転移現象を示す。
後悔はパワーローから臨界指数 $\alpha=\frac{1}{2} での定数への変化を束縛する。
この結果は、Even-Darらによって提起されたオープンな問題を解決します。
[2009]特定パラメーター制度におけるオンラインジョブスケジューリング問題に対する効率的なノンレグレットポリシーの設計について。
本研究の結果は,非加法的大域的報酬関数の将来勾配の欲求的推定,適応的後悔境界のブートストラップなど,新たなアルゴリズム的・解析的手法を導入している。
関連論文リスト
- Online Resource Allocation in Episodic Markov Decision Processes [1.8416014644193066]
本稿では, 有限水平制約マルコフ決定過程におけるオンライン割当問題として, 問題を定式化する。
本稿では,観測・観測・観測・観測体制の整備と既存の決定・観測体制の改善について述べる。
平均報酬と平均資源消費関数にアクセスできる静的最適政策に対する後悔は、高い確率で$tilde O(rho-1H3/2SsqrtAT)$で束縛されていることを示す。
論文 参考訳（メタデータ） (2023-05-18T06:28:34Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Autoregressive Bandits [58.46584210388307]
本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。
報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。
次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
論文 参考訳（メタデータ） (2022-12-12T21:37:36Z) - Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear
Contextual Bandits and Markov Decision Processes [59.61248760134937]
本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。
提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。
本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
論文 参考訳（メタデータ） (2022-12-12T15:04:56Z) - Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning
with Linear Function Approximation [16.871660060209674]
本研究では, 線形関数近似を用いた展開効率向上強化学習(RL)の課題を, 遠近自由探索条件下で検討する。
我々は,最大$widetildeO(fracd2H5epsilon2)$ trajectoriesを$H$デプロイメント内で収集し,$epsilon$-Optimal Policyを任意の(おそらくはデータに依存した)報酬関数の選択に対して識別するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-10-03T03:48:26Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Online Allocation with Two-sided Resource Constraints [44.5635910908944]
我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。
提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-28T02:21:06Z) - Fairer LP-based Online Allocation [13.478067250930101]
本稿では,リニアプログラム(LP)に基づくオンラインリソース割り当て問題について考察する。
内部点LPソルバを用いて不公平な資源支出を動的に検出するフェアアルゴリズムを提案する。
提案手法は最適化インスタンスの制約としてフェアネス要件を定式化せず,アルゴリズム設計の観点からこの問題に対処する。
論文 参考訳（メタデータ） (2021-10-27T17:45:20Z) - Online Sub-Sampling for Reinforcement Learning with General Function
Approximation [111.01990889581243]
本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。
複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。
少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
論文 参考訳（メタデータ） (2021-06-14T07:36:25Z) - Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
本稿では, 総資源消費に作用する非線形正規化器を含む変種である, 語彙化オンライン割当問題を紹介する。
この問題では、要求は時間とともに繰り返し届き、各要求に対して、意思決定者は報酬を生成しリソースを消費するアクションを取る必要があります。
目的は、資源制約を受ける加算可分な報酬と非分離可正則化器の値とを同時に最大化することである。
論文 参考訳（メタデータ） (2020-07-01T14:24:58Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳（メタデータ） (2020-03-02T05:02:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。