論文の概要: Bandit Algorithms for Prophet Inequality and Pandora's Box
- arxiv url: http://arxiv.org/abs/2211.08586v2
- Date: Thu, 7 Dec 2023 03:44:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-08 21:29:07.092207
- Title: Bandit Algorithms for Prophet Inequality and Pandora's Box
- Title（参考訳）: 預言不等式に対するバンディットアルゴリズムとpandoraの箱
- Authors: Khashayar Gatmiry, Thomas Kesselheim, Sahil Singla, and Yifan Wang
- Abstract要約: マルチアーメッド・バンディットモデルにおける預言不等式とPandoraのボックス問題について検討した。
我々の結果は、予言の不平等とPandoraのBoxの両面で、ほぼ最適の$tildeO(mathsfpoly(n)sqrtT)$トータル後悔アルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 13.709418181148148
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Prophet Inequality and Pandora's Box problems are fundamental stochastic
problem with applications in Mechanism Design, Online Algorithms, Stochastic
Optimization, Optimal Stopping, and Operations Research. A usual assumption in
these works is that the probability distributions of the $n$ underlying random
variables are given as input to the algorithm. Since in practice these
distributions need to be learned, we initiate the study of such stochastic
problems in the Multi-Armed Bandits model.
In the Multi-Armed Bandits model we interact with $n$ unknown distributions
over $T$ rounds: in round $t$ we play a policy $x^{(t)}$ and receive a partial
(bandit) feedback on the performance of $x^{(t)}$. The goal is to minimize the
regret, which is the difference over $T$ rounds in the total value of the
optimal algorithm that knows the distributions vs. the total value of our
algorithm that learns the distributions from the partial feedback. Our main
results give near-optimal $\tilde{O}(\mathsf{poly}(n)\sqrt{T})$ total regret
algorithms for both Prophet Inequality and Pandora's Box.
Our proofs proceed by maintaining confidence intervals on the unknown indices
of the optimal policy. The exploration-exploitation tradeoff prevents us from
directly refining these confidence intervals, so the main technique is to
design a regret upper bound that is learnable while playing low-regret Bandit
policies.
- Abstract（参考訳）: 預言不等式とpandoraのボックス問題は、メカニズム設計、オンラインアルゴリズム、確率的最適化、最適停止、運用研究における応用における基本的な確率的問題である。
これらの研究における通常の仮定は、n$の確率変数の確率分布がアルゴリズムへの入力として与えられることである。
実際にこれらの分布を学習する必要があるため、マルチアーメッド帯域モデルにおけるそのような確率的問題の研究を開始する。
ラウンド$t$では、ポリシー$x^{(t)}$を再生し、$x^{(t)}$のパフォーマンスに関する部分的な(バンド)フィードバックを受け取ります。
目的は,分布を学習するアルゴリズムの総値と,部分的フィードバックから分布を学習するアルゴリズムの総値との合計値におけるT$ラウンドの差を最小化することである。
我々の主な結果は、預言不等式とpandoraの箱の両方に対して、ほぼ最適の$\tilde{o}(\mathsf{poly}(n)\sqrt{t})$ total regretアルゴリズムを与える。
我々の証明は、最適政策の未知の指標に対する信頼区間を維持することによって進められる。
探索と爆発のトレードオフは、これらの信頼区間を直接精査することを妨げるため、主なテクニックは、低レグレットのバンディットポリシーを実行しながら学習可能な後悔の上限を設計することである。
関連論文リスト
- Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。
Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。
特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
論文 参考訳（メタデータ） (2024-03-15T23:36:55Z) - Semi-Bandit Learning for Monotone Stochastic Optimization [20.776114616154242]
モノトーン」問題のクラスに対して汎用的なオンライン学習アルゴリズムを提供する。
我々のフレームワークは、預言者、Pandoraのボックスナップサック、不等式マッチング、部分モジュラー最適化など、いくつかの基本的な最適化問題に適用できる。
論文 参考訳（メタデータ） (2023-12-24T07:46:37Z) - Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。
我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。
V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-19T01:09:24Z) - Maillard Sampling: Boltzmann Exploration Done Optimally [11.282341369957216]
この論文は、$K$武装バンディット問題に対するランダム化アルゴリズムを示す。
メイラードサンプリング(MS)は、各アームを閉じた形で選択する確率を計算する。
最適性を失わずに$sqrtKTlogK$に制限された最小値を改善するMS$+$というMSの変種を提案する。
論文 参考訳（メタデータ） (2021-11-05T06:50:22Z) - Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits
with Super Heavy-Tailed Payoffs [27.636407641546914]
実験的な中央値列の経験的平均を計算し,確率変数を推定する,新しい頑健な統計推定器を提案する。
非常に重みのある雑音であっても, 後悔の限界がほぼ最適であることを示す。
論文 参考訳（メタデータ） (2021-10-26T17:30:44Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳（メタデータ） (2021-10-25T02:53:24Z) - No Regrets for Learning the Prior in Bandits [30.478188057004175]
$tt AdaTS$は、バンディットタスクに順次適応するトンプソンサンプリングアルゴリズムである。
$tt AdaTS$は、バンドイト問題のいくつかのクラスで効率的に実装できる完全ベイズアルゴリズムである。
論文 参考訳（メタデータ） (2021-07-13T15:51:32Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial
Rewards [59.559028338399855]
我々は,行動セットと敵意の報酬を伴って睡眠中の盗賊の問題を考察する。
本稿では,EXP3にインスパイアされた新しい計算効率のよいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-14T00:41:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。