論文の概要: Robust Bandit Learning with Imperfect Context
- arxiv url: http://arxiv.org/abs/2102.05018v1
- Date: Tue, 9 Feb 2021 18:35:33 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-10 14:56:53.600422
- Title: Robust Bandit Learning with Imperfect Context
- Title(参考訳): 不完全文脈を用いたロバスト帯域学習
- Authors: Jianyi Yang, Shaolei Ren
- Abstract要約: 本研究では,腕の選択に不完全なコンテキストのみを使用可能なコンテキスト的マルチアームバンディットについて検討する。
我々は、最悪の場合の報酬を最大化するMaxMinUCBと、最悪の場合の後悔を最小限に抑えるMinWDの2つの堅牢なアーム選択アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 15.658214603209458
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A standard assumption in contextual multi-arm bandit is that the true context
is perfectly known before arm selection. Nonetheless, in many practical
applications (e.g., cloud resource management), prior to arm selection, the
context information can only be acquired by prediction subject to errors or
adversarial modification. In this paper, we study a contextual bandit setting
in which only imperfect context is available for arm selection while the true
context is revealed at the end of each round. We propose two robust arm
selection algorithms: MaxMinUCB (Maximize Minimum UCB) which maximizes the
worst-case reward, and MinWD (Minimize Worst-case Degradation) which minimizes
the worst-case regret. Importantly, we analyze the robustness of MaxMinUCB and
MinWD by deriving both regret and reward bounds compared to an oracle that
knows the true context. Our results show that as time goes on, MaxMinUCB and
MinWD both perform as asymptotically well as their optimal counterparts that
know the reward function. Finally, we apply MaxMinUCB and MinWD to online edge
datacenter selection, and run synthetic simulations to validate our theoretical
analysis.
- Abstract(参考訳): 文脈的マルチアームバンディットの標準的な仮定真のコンテキストは、腕の選択の前に完全に知られているということです。
それでも、多くの実用的なアプリケーション(例えばクラウドリソース管理)では、arm選択の前にコンテキスト情報は、エラーや逆の修正を受けた予測によってのみ取得できる。
本稿では,各ラウンドの最後に真のコンテキストを明かしながら,アーム選択において不完全コンテキストのみを利用可能とするコンテキストバンディット設定について検討する。
最悪の報酬を最大化するMaxMinUCB(Maximize Minimum UCB)と最悪の後悔を最小限に抑えるMinWD(Minimize Worst-case Degradation)の2つの堅牢なアーム選択アルゴリズムを提案します。
重要なことは、MaxMinUCBとMinWDの堅牢性を分析し、真のコンテキストを知っているオラクルと比較して、後悔と報酬の境界の両方を導き出します。
以上の結果から,MaxMinUCBとMinWDはともに漸近的に,報酬関数を知っていれば最適であることがわかった。
最後に、MaxMinUCBとMinWDをオンラインエッジデータセンタの選択に適用し、理論解析を検証するために合成シミュレーションを実行します。
関連論文リスト
- A Minimaximalist Approach to Reinforcement Learning from Human Feedback [53.05529717075474]
人間のフィードバックから強化学習を行うアルゴリズムとして,SPO(Self-Play Preference Optimization)を提案する。
我々のアプローチは、報酬モデルや不安定な敵の訓練を必要としないという点で最小主義である。
一連の継続的制御タスクにおいて、報酬ベースのアプローチよりもはるかに効率的に学習できることを実証します。
論文 参考訳(メタデータ) (2024-01-08T17:55:02Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [56.457634640638254]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳(メタデータ) (2023-10-02T08:15:52Z) - Proportional Response: Contextual Bandits for Simple and Cumulative
Regret Minimization [29.579719765255927]
本稿では,文脈的帯域幅設定のための効率的な帯域幅アルゴリズムのファミリーを提案する。
我々のアルゴリズムは任意の関数クラスで動作し、不特定性をモデル化するのに堅牢で、連続したアーム設定で使用できます。
論文 参考訳(メタデータ) (2023-07-05T08:34:54Z) - Stochastic Contextual Dueling Bandits under Linear Stochastic
Transitivity Models [25.336599480692122]
我々は,コンテキスト情報を用いた決闘バンディット問題における後悔の最小化タスクについて検討する。
本稿では,フィードバックプロセスの模倣に基づく計算効率のよいアルゴリズムである$texttCoLSTIM$を提案する。
本実験は,CoLSTモデルの特殊事例に対する最先端アルゴリズムよりも優れていることを示す。
論文 参考訳(メタデータ) (2022-02-09T17:44:19Z) - Deep Upper Confidence Bound Algorithm for Contextual Bandit Ranking of
Information Selection [0.0]
CMAB(Contextual Multi-armed bandits)は、ユーザの関心に応じて情報のフィルタリングと優先順位付けを学習するために広く使用されている。
本研究は,トップKアームを反復的に選択して報酬を最大化するCMABフレームワークに基づくトップKランキングの分析である。
本稿では,Deep Up Confidence Bound (UCB)アルゴリズムという新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-10-08T13:32:14Z) - Restless-UCB, an Efficient and Low-complexity Algorithm for Online
Restless Bandits [61.490254407420906]
我々は、各腕の状態がマルコフ連鎖に従って進化するオンラインレス・バンディット問題について研究する。
本研究では,探索研究の枠組みに従う学習方針であるReestless-UCBを提案する。
論文 参考訳(メタデータ) (2020-11-05T05:16:04Z) - Nearly Dimension-Independent Sparse Linear Bandit over Small Action
Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。
この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。
本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文 参考訳(メタデータ) (2020-09-04T04:10:39Z) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳(メタデータ) (2020-08-10T08:30:52Z) - On Regret with Multiple Best Arms [12.315392649501101]
バンディット設定における複数のベスト/ニア最適アームの存在に関する後悔問題について検討する。
我々の目標は、問題の未知の硬さに自動的に適応できるアルゴリズムを設計することです。
論文 参考訳(メタデータ) (2020-06-26T04:01:46Z) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳(メタデータ) (2020-03-05T21:29:27Z) - Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。
提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-20T06:36:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。