論文の概要: Constrained regret minimization for multi-criterion multi-armed bandits

• arxiv url: http://arxiv.org/abs/2006.09649v1
• Date: Wed, 17 Jun 2020 04:23:18 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-19 19:35:19.396441
• Title: Constrained regret minimization for multi-criterion multi-armed bandits
• Title（参考訳）: 多基準多腕バンディットに対する制約付き後悔最小化
• Authors: Anmol Kagrecha, Jayakrishnan Nair, Krishna Jagannathan
• Abstract要約: リスク制約を条件として,所与の時間的地平線上での後悔の最小化の問題について検討する。 本稿では,対数的後悔を保証するリスク制約付き低信頼境界アルゴリズムを提案する。 我々は,リスク制約付き後悔最小化アルゴリズムの性能に低い限界を証明した。
• 参考スコア（独自算出の注目度）: 5.349852254138086
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a stochastic multi-armed bandit setting and study the problem of regret minimization over a given time horizon, subject to a risk constraint. Each arm is associated with an unknown cost/loss distribution. The learning agent is characterized by a risk-appetite that she is willing to tolerate, which we model using a pre-specified upper bound on the Conditional Value at Risk (CVaR). An optimal arm is one that minimizes the expected loss, among those arms that satisfy the CVaR constraint. The agent is interested in minimizing the number of pulls of suboptimal arms, including the ones that are 'too risky.' For this problem, we propose a Risk-Constrained Lower Confidence Bound (RC-LCB) algorithm, that guarantees logarithmic regret, i.e., the average number of plays of all non-optimal arms is at most logarithmic in the horizon. The algorithm also outputs a boolean flag that correctly identifies with high probability, whether the given instance was feasible/infeasible with respect to the risk constraint. We prove lower bounds on the performance of any risk-constrained regret minimization algorithm and establish a fundamental trade-off between regret minimization and feasibility identification. The proposed algorithm and analyses can be readily generalized to solve constrained multi-criterion optimization problems in the bandits setting.
• Abstract（参考訳）: 我々は, 確率的多腕バンディット設定を検討し, リスク制約を前提として, 与えられた時間軸上の後悔の最小化問題を検討する。 各アームは未知のコスト/損失分布に関連付けられる。 学習エージェントは、リスクに対する条件付値(cvar)を事前に指定した上限を用いてモデル化し、許容するリスク評価によって特徴付けられる。 最適アームは、CVaR制約を満たすアームのうち、期待される損失を最小限に抑えるものである。 エージェントは、"危険すぎる"ものを含む、最適下腕の引き金の数を最小化することに興味がある。 そこで本研究では,非オプティカルアームの遊び数の平均値が対数的であり,対数的後悔を保証できるリスク制約付き低信頼境界(rc-lcb)アルゴリズムを提案する。 アルゴリズムはまた、与えられたインスタンスがリスク制約に関して実行可能か実行不可能かを、高い確率で正確に識別するブールフラグを出力する。 リスク制約付き後悔最小化アルゴリズムの性能に低い限界を証明し、後悔最小化と実現可能性識別の基本的なトレードオフを確立する。 提案アルゴリズムと解析は,バンディット設定における制約付き多重基準最適化問題を解くために容易に一般化できる。

関連論文リスト

• Planning and Learning in Risk-Aware Restless Multi-Arm Bandit Problem [4.178382980763478]
  レスレス・マルチアーム・バンディットでは、中央エージェントは複数のバンドイット(アーム)に限られたリソースを最適に分散させる。 本研究では,リスク・アウェアネスを組み込むことにより,従来のレスレスト・マルチアーム・バンディット問題をリスクニュートラル目標に一般化する。 我々は、リスク認識対象の指標可能性条件を確立し、Whittleインデックスに基づくソリューションを提供する。
  論文  参考訳（メタデータ） (2024-10-30T13:59:30Z)
• Best Arm Identification with Minimal Regret [55.831935724659175]
  最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。 エージェントの目標は、所定の信頼度で最高の腕を特定することである。 二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
  論文  参考訳（メタデータ） (2024-09-27T16:46:02Z)
• Minimax Linear Regression under the Quantile Risk [31.277788690403522]
  量子リスク下での線形回帰におけるミニマックス法の設計問題について検討する。 我々は,最近提案されたmin-max回帰法の変種における最悪のケース量子化リスクに一致する上限を証明した。
  論文  参考訳（メタデータ） (2024-06-17T23:24:14Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimization [29.579719765255927]
  本稿では,文脈的帯域幅設定のための効率的な帯域幅アルゴリズムのファミリーを提案する。 我々のアルゴリズムは任意の関数クラスで動作し、不特定性をモデル化するのに堅牢で、連続したアーム設定で使用できます。
  論文  参考訳（メタデータ） (2023-07-05T08:34:54Z)
• Risk-aware linear bandits with convex loss [0.0]
  提案手法は, 線形帯域幅の一般化に類似した, 最適リスク認識動作を学習するための楽観的 UCB アルゴリズムを提案する。 このアプローチではアルゴリズムの各ラウンドで凸問題を解く必要があり、オンライン勾配降下法によって得られる近似解のみを許すことで緩和することができる。
  論文  参考訳（メタデータ） (2022-09-15T09:09:53Z)
• Safe Online Bid Optimization with Return-On-Investment and Budget Constraints subject to Uncertainty [87.81197574939355]
  最適化問題と学習問題の両方について検討する。 我々は、潜在的に線形な数の制約違反を犠牲にして、サブ線形後悔を保証するアルゴリズム、すなわちGCBを提供する。 より興味深いことに、我々はGCB_safe(psi,phi)というアルゴリズムを提供し、サブ線形擬似回帰と安全性w.h.p.の両方を、耐性 psi と phi を受け入れるコストで保証する。
  論文  参考訳（メタデータ） (2022-01-18T17:24:20Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。 大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。 リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
  論文  参考訳（メタデータ） (2021-08-25T17:09:01Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。 我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。 我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2020-02-01T15:33:50Z)

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

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