論文の概要: Approximately Stationary Bandits with Knapsacks
- arxiv url: http://arxiv.org/abs/2302.14686v2
- Date: Sat, 8 Jul 2023 22:16:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-11 18:44:12.060195
- Title: Approximately Stationary Bandits with Knapsacks
- Title（参考訳）: クナプサックによる約定置帯
- Authors: Giannis Fikioris, \'Eva Tardos
- Abstract要約: Knapsacks (BwK) は、世界的な予算制約の下でのバンドイッツ問題の一般化である。
これまでの研究では、各ラウンドのリソースの報酬と消費がi.d.分布からサンプリングされるBwKと、これらのパラメータが相手によって選択されるAdversarial BwKの2つの極端に焦点が当てられていた。
私たちの仕事は、このギャップを埋めることを目的としています。
- 参考スコア（独自算出の注目度）: 0.30458514384586405
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Bandits with Knapsacks (BwK), the generalization of the Bandits problem under
global budget constraints, has received a lot of attention in recent years.
Previous work has focused on one of the two extremes: Stochastic BwK where the
rewards and consumptions of the resources of each round are sampled from an
i.i.d. distribution, and Adversarial BwK where these parameters are picked by
an adversary. Achievable guarantees in the two cases exhibit a massive gap:
No-regret learning is achievable in the stochastic case, but in the adversarial
case only competitive ratio style guarantees are achievable, where the
competitive ratio depends either on the budget or on both the time and the
number of resources. What makes this gap so vast is that in Adversarial BwK the
guarantees get worse in the typical case when the budget is more binding. While
``best-of-both-worlds'' type algorithms are known (single algorithms that
provide the best achievable guarantee in each extreme case), their bounds
degrade to the adversarial case as soon as the environment is not fully
stochastic.
Our work aims to bridge this gap, offering guarantees for a workload that is
not exactly stochastic but is also not worst-case. We define a condition,
Approximately Stationary BwK, that parameterizes how close to stochastic or
adversarial an instance is. Based on these parameters, we explore what is the
best competitive ratio attainable in BwK. We explore two algorithms that are
oblivious to the values of the parameters but guarantee competitive ratios that
smoothly transition between the best possible guarantees in the two extreme
cases, depending on the values of the parameters. Our guarantees offer great
improvement over the adversarial guarantee, especially when the available
budget is small. We also prove bounds on the achievable guarantee, showing that
our results are approximately tight when the budget is small.
- Abstract（参考訳）: 世界的な予算制約の下でのバンディット問題の一般化であるナップサック(bwk)によるバンディットは近年注目を集めている。
以前の研究では、各ラウンドのリソースの報酬と消費がi.d.分布からサンプリングされる確率的BwKと、これらのパラメータが相手によって選択される逆BwKの2つの極端に焦点が当てられていた。
非回帰学習は確率的な場合では達成可能であるが、敵対的な場合においては競争比率のスタイルのみが達成可能であり、競争比率は予算か時間と資源の双方に左右される。
このギャップを大きくしているのは、Adversarial BwKでは、予算がより拘束力のある場合、保証が悪化することです。
best-of-both-worlds''型アルゴリズムは知られているが(各極端な場合において最高の保証を提供する単一のアルゴリズム)、それらの境界は、環境が完全に確率的でないとすぐに敵のケースに分解される。
私たちの仕事は、このギャップを埋めることを目的としており、厳密には確率的ではなく最悪のケースでもないワークロードの保証を提供しています。
我々は、インスタンスが確率的あるいは逆数的に近いかをパラメータ化する条件 A approximately Stationary BwK を定義する。
これらのパラメータに基づいて、BwKで達成可能な最高の競争比率を探索する。
パラメータの値に従わない2つのアルゴリズムを探索し、パラメータの値に依存する2つの極端なケースにおいて、最善の保証間のスムーズな遷移が可能な競合比を保証する。
我々の保証は、特に利用可能な予算が少なければ、敵の保証を大きく改善します。
私たちはまた、達成可能な保証の限界を証明し、予算が小さい場合の結果がほぼタイトであることを示します。
関連論文リスト
- Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Equal Opportunity of Coverage in Fair Regression [50.76908018786335]
我々は、予測の不確実性の下で公正な機械学習(ML)を研究し、信頼性と信頼性のある意思決定を可能にする。
本研究は,(1)類似した結果の異なる集団に対するカバー率が近いこと,(2)人口全体のカバー率が一定水準にあること,の2つの特性を達成することを目的としたカバーの平等機会(EOC)を提案する。
論文 参考訳（メタデータ） (2023-11-03T21:19:59Z) - Best of Both Worlds Model Selection [39.211071446838474]
ネストされた政策クラスが存在する場合のバンディットシナリオにおけるモデル選択の問題について検討する。
私たちのアプローチでは、各ベース学習者は、保持するかもしれないし持たないかもしれない後悔の候補を伴わなければならない。
これらは、(線形)バンディットのシナリオでモデル選択を行いながら、(確率的および敵対的)双方の保証を最大限に達成する最初の理論的結果である。
論文 参考訳（メタデータ） (2022-06-29T20:57:30Z) - Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
オンライン学習の課題として,意思決定者が,リソース制約の有限セットに違反することなく,期待する報酬を最大化したい,という課題を提起する。
当社のフレームワークは,意思決定者がそのエビデンスを柔軟かつコスト論的に扱えるようにします。
論文 参考訳（メタデータ） (2022-02-28T12:10:48Z) - Optimal Fixed-Budget Best Arm Identification using the Augmented Inverse
Probability Estimator in Two-Armed Gaussian Bandits with Unknown Variances [27.122181278234617]
両腕のガウスバンドにおける固定予算ベストアーム識別問題について検討する。
本稿では,アームドローの目標配置確率を推定し,ランダム化サンプリング(RS)を用いたサンプリングルールを含む戦略を提案する。
提案手法は,サンプルサイズが無限大になり,両腕間のギャップがゼロとなる場合に,不可視的に最適であることを示す。
論文 参考訳（メタデータ） (2022-01-12T13:38:33Z) - Private Robust Estimation by Stabilizing Convex Relaxations [22.513117502159922]
$(epsilon, delta)$-differentially private (DP)
$(epsilon, delta)$-differentially private (DP)
$(epsilon, delta)$-differentially private (DP)
論文 参考訳（メタデータ） (2021-12-07T07:47:37Z) - Fair Classification with Adversarial Perturbations [35.030329189029246]
本研究は,学習サンプルの任意の$eta$-fractionを選択でき,保護属性を任意に摂動することができるような,万能な逆境の存在下での公平な分類について検討する。
我々の主な貢献は、精度と公正性に関する証明可能な保証を伴うこの逆条件で公平な分類法を学ぶための最適化フレームワークである。
我々は、自然な仮説クラスに対する我々のフレームワークの保証のほぼ正当性を証明している: どのアルゴリズムもはるかに精度が良く、より良い公正性を持つアルゴリズムは、より低い精度でなければならない。
論文 参考訳（メタデータ） (2021-06-10T17:56:59Z) - On Lower Bounds for Standard and Robust Gaussian Process Bandit
Optimization [55.937424268654645]
有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。
本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
論文 参考訳（メタデータ） (2020-08-20T03:48:14Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z) - Robust Optimization for Fairness with Noisy Protected Groups [85.13255550021495]
ノイズが保護されたグループラベルに頼った結果について検討した。
頑健な最適化を用いた2つの新しいアプローチを提案する。
頑健なアプローチは、単純アプローチよりも真のグループ公平性を保証することが示される。
論文 参考訳（メタデータ） (2020-02-21T14:58:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。