論文の概要: Combinatorial Rising Bandit
- arxiv url: http://arxiv.org/abs/2412.00798v2
- Date: Mon, 03 Feb 2025 09:25:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-04 15:57:53.370618
- Title: Combinatorial Rising Bandit
- Title(参考訳): Combinatorial Rising Bandit
- Authors: Seockbean Song, Youngsik Yoon, Siwei Wang, Wei Chen, Jungseul Ok,
- Abstract要約: 我々は,政策後悔を最小限に抑えるために,帯域の増大という問題を提起し,コンビネーション・ライジング・アッパー・信頼境界 (CRUCB) と呼ばれる証明可能なアルゴリズムを提案する。
CRUCBは、後悔の上限が後悔の下限に近いことを示すことにより、確実に効率的である。
さらに,CRUCBの有効性と優位性を,合成環境だけでなく,深層強化学習の現実的応用においても実証的に実証した。
- 参考スコア(独自算出の注目度): 29.357803270943254
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Combinatorial online learning is a fundamental task to decide the optimal combination of base arms in sequential interactions with systems providing uncertain rewards, which is applicable to diverse domains such as robotics, social advertising, network routing and recommendation systems. In real-world scenarios, we often observe rising rewards, where the selection of a base arm not only provides an instantaneous reward but also contributes to the enhancement of future rewards, {\it e.g.}, robots enhancing proficiency through practice and social influence strengthening in the history of successful recommendations. To address this, we introduce the problem of combinatorial rising bandit to minimize policy regret and propose a provably efficient algorithm, called Combinatorial Rising Upper Confidence Bound (CRUCB), of which regret upper bound is close to a regret lower bound. To the best of our knowledge, previous studies do not provide a sub-linear regret lower bound, making it impossible to assess the efficiency of their algorithms. However, we provide the sub-linear regret lower bound for combinatorial rising bandit and show that CRUCB is provably efficient by showing that the regret upper bound is close to the regret lower bound. In addition, we empirically demonstrate the effectiveness and superiority of CRUCB not only in synthetic environments but also in realistic applications of deep reinforcement learning.
- Abstract(参考訳): 組合せオンライン学習は、ロボット工学、ソーシャル広告、ネットワークルーティング、レコメンデーションシステムといった様々な分野に適用可能な、不確実な報酬を提供するシステムとの逐次的な相互作用におけるベースアームの最適な組み合わせを決定するための基本的なタスクである。
実世界のシナリオでは、しばしば報酬の上昇を観察し、ベースアームの選択は即時報酬を提供するだけでなく、将来の報酬の強化にも寄与する。
これを解決するために、政策後悔を最小限に抑えるために組合せ的上昇帯域の問題を導入し、後悔の上界が後悔の低い下界に近くなる「コンビネーション・ライジング・アッパー・信頼境界」(CRUCB)と呼ばれる証明可能なアルゴリズムを提案する。
我々の知識を最大限に活用するために、過去の研究では、サブリニアな後悔の少ない境界を提供しておらず、アルゴリズムの効率を評価することは不可能である。
しかし, 組合せ的上昇バンディットに対するサブ線形後悔下限を提示し, 後悔上限が後悔下限に近いことを示すことにより, CRUCBが有効であることを示す。
さらに,CRUCBの有効性と優位性を,合成環境だけでなく,深層強化学習の現実的応用においても実証的に実証した。
関連論文リスト
- Fair Algorithms with Probing for Multi-Agent Multi-Armed Bandits [15.700062892888084]
我々は、割り当て前に選択した武器に関する情報を戦略的に収集する新しい探索フレームワークを導入する。
報奨分布が知られているオフライン環境では、準モジュラ特性を利用して、証明可能な性能境界を持つ欲求探索アルゴリズムを設計する。
より複雑なオンライン設定では、公平性を維持しながらサブ線形後悔を実現するアルゴリズムを開発する。
論文 参考訳(メタデータ) (2025-06-17T21:43:21Z) - Recursive Deep Inverse Reinforcement Learning [16.05411507856928]
対向計画や非協調型マルチエージェントシステムにおいては,相手の行動から相手の目標を推定することが重要である。
本稿では, 対向行動と目標を管理する費用関数を復元するオンライン逆強化学習(RDIRL)手法を提案する。
論文 参考訳(メタデータ) (2025-04-17T17:39:35Z) - Reinforcement learning with combinatorial actions for coupled restless bandits [62.89013331120493]
提案するSEQUOIAは,動作空間に対する長期報酬を直接最適化するRLアルゴリズムである。
我々は,複数介入,経路制約,二部間マッチング,容量制約という,制約を伴う4つの新しいレスレス・バンディット問題に対して,SEQUOIAを実証的に検証した。
論文 参考訳(メタデータ) (2025-03-01T21:25:21Z) - Online Clustering of Dueling Bandits [59.09590979404303]
本稿では、優先フィードバックに基づく協調的な意思決定を可能にするために、最初の「デュエルバンディットアルゴリズムのクラスタリング」を導入する。
本稿では,(1)ユーザ報酬関数をコンテキストベクトルの線形関数としてモデル化する線形デューリング帯域のクラスタリング(COLDB)と,(2)ニューラルネットワークを用いて複雑な非線形ユーザ報酬関数をモデル化するニューラルデューリング帯域のクラスタリング(CONDB)の2つの新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2025-02-04T07:55:41Z) - Offline Learning for Combinatorial Multi-armed Bandits [56.96242764723241]
Off-CMABはCMABの最初のオフライン学習フレームワークである。
Off-CMABは悲観的な報酬推定と解法を組み合わせる。
合成および実世界のデータセットの実験は、CLCBの優れた性能を強調している。
論文 参考訳(メタデータ) (2025-01-31T16:56:18Z) - Best Arm Identification with Minimal Regret [55.831935724659175]
最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。
エージェントの目標は、所定の信頼度で最高の腕を特定することである。
二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
論文 参考訳(メタデータ) (2024-09-27T16:46:02Z) - Neural Dueling Bandits [58.90189511247936]
ニューラルネットワークを用いて、予め選択した腕の好みフィードバックを用いて報酬関数を推定する。
次に、理論結果を二項フィードバックによる文脈的帯域幅問題に拡張し、それはそれ自体は自明な寄与ではない。
論文 参考訳(メタデータ) (2024-07-24T09:23:22Z) - MultiSlot ReRanker: A Generic Model-based Re-Ranking Framework in
Recommendation Systems [6.0232112783722]
本稿では,汎用モデルに基づくリグレードフレームワークであるMultiSlot ReRankerを提案し,その妥当性,多様性,鮮度を同時に最適化する。
我々は,OpenAI GymをRayフレームワークに統合したマルチスロットリグレードシミュレータを構築した。
論文 参考訳(メタデータ) (2024-01-11T23:17:07Z) - Bandits Meet Mechanism Design to Combat Clickbait in Online
Recommendation [50.469872635246176]
我々は,マルチアームバンディット問題の戦略的変種について検討し,これを戦略的クリックバンディット(Click-bandit)と呼ぶ。
このモデルは、推奨項目の選択がクリックスルー率とクリック後の報酬の両方に依存するオンラインレコメンデーションのアプリケーションによって動機付けられている。
論文 参考訳(メタデータ) (2023-11-27T09:19:01Z) - Master-slave Deep Architecture for Top-K Multi-armed Bandits with
Non-linear Bandit Feedback and Diversity Constraints [21.109631268204215]
本稿では,トップ$Kのマルチアームバンディット問題を解決するために,新しいマスタースレーブアーキテクチャを提案する。
我々の知る限りでは、バンドイットフィードバックの下で多様性の制約を考慮に入れた最初のバンドイットである。
論文 参考訳(メタデータ) (2023-08-24T09:39:04Z) - Bayesian Regret Minimization in Offline Bandits [35.7981453841683]
オフライン線形包帯におけるベイズ的後悔を最小限に抑える決定の仕方について検討する。
LCBへの依存は本質的にこの設定に欠陥がある、と我々は主張する。
我々の限界は金融リスク対策への新たなつながりに大きく依存している。
論文 参考訳(メタデータ) (2023-06-02T02:05:02Z) - Anti-Exploration by Random Network Distillation [63.04360288089277]
ランダムネットワーク蒸留 (RND) の条件付けは, 不確実性推定器として用いるのに十分な識別性がないことを示す。
この制限は、FiLM(Feature-wise Linear Modulation)に基づく条件付けによって回避できることを示す。
D4RLベンチマークで評価したところ、アンサンブルベースの手法に匹敵する性能を達成でき、アンサンブルのない手法よりも広いマージンで性能を向上できることがわかった。
論文 参考訳(メタデータ) (2023-01-31T13:18:33Z) - Contextual bandits with concave rewards, and an application to fair
ranking [108.48223948875685]
CBCR (Contextual Bandits with Concave Rewards) に対する反省点のある最初のアルゴリズムを提案する。
我々は,スカラー・リワード問題に対するCBCRの後悔から,新たな縮小を導出した。
推薦の公正さによって動機づけられたCBCRの特別事例として,ランク付けと公正を意識した目的について述べる。
論文 参考訳(メタデータ) (2022-10-18T16:11:55Z) - Distributional Reward Estimation for Effective Multi-Agent Deep
Reinforcement Learning [19.788336796981685]
実効的マルチエージェント強化学習(DRE-MARL)のための分散逆推定フレームワークを提案する。
本研究の目的は,安定トレーニングのための多行動分岐報酬推定と政策重み付け報酬アグリゲーションを設計することである。
DRE-MARLの優位性は,有効性とロバスト性の両方の観点から,SOTAベースラインと比較して,ベンチマークマルチエージェントシナリオを用いて実証される。
論文 参考訳(メタデータ) (2022-10-14T08:31:45Z) - Versatile Dueling Bandits: Best-of-both-World Analyses for Online
Learning from Preferences [28.79598714109439]
両環境および敵環境における$K$武器のデュエルバンディットの問題について検討する。
まず,マルチアームのバンディットに対して,任意の(一般的な)デュエル・バンドレットから新たなリダクションを提案する。
提案アルゴリズムは,コンドルチェット・ウィンナーベンチマークに対して最適な$O(sum_i = 1K fraclog TDelta_i)$ regret boundを達成した最初のアルゴリズムでもある。
論文 参考訳(メタデータ) (2022-02-14T13:37:23Z) - Robust Upper Bounds for Adversarial Training [4.971729553254843]
敵の損失の上限を最小化することで、敵の訓練に新たなアプローチを導入する。
このバウンダリは、各レイヤの別々のバウンダリではなく、ネットワークの全体的拡張に基づいている。
提案手法により2つの新しい手法を導出する。
論文 参考訳(メタデータ) (2021-12-17T01:52:35Z) - Contextual Combinatorial Multi-output GP Bandits with Group Constraints [11.317136648551537]
連合型多武装バンディット問題では、クライアントを保護するための最小限のプライバシー要件を満たしながら、世界的報酬を最大化することが主な目標である。
我々は、グループやアクションセットの変更によるコンテキスト的バンディットの設定を検討し、そこでは、類似のベースアームがグループに到着し、スーパーアームと呼ばれるベースアームのセットが各ラウンドで選択され、スーパーアームの報酬を最大化し、ベースアームが選択されたグループの報酬の制約を満たす。
次に、累積スーパーアーム報酬の最大化と充足のバランスをとる、Thresholded Combinatored upper Confidence Bounds (TCGP-UCB)と呼ばれる新しい二重UCBGPバンドアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-11-29T18:39:09Z) - DORB: Dynamically Optimizing Multiple Rewards with Bandits [101.68525259222164]
政策に基づく強化学習は、言語生成タスクにおいて、微分不可能な評価指標を最適化するための有望なアプローチであることが証明されている。
We use the Exp3 algorithm for bandit and formulate two approach for bandit rewards: (1) Single Multi-reward Bandit (SM-Bandit), (2) Hierarchical Multi-reward Bandit (HM-Bandit)
我々は,2つの重要なNLGタスクにおいて,様々な自動計測と人的評価を通じて,我々のアプローチの有効性を実証的に示す。
論文 参考訳(メタデータ) (2020-11-15T21:57:47Z) - Instance-Dependent Complexity of Contextual Bandits and Reinforcement
Learning: A Disagreement-Based Perspective [104.67295710363679]
古典的なマルチアームバンディット問題において、インスタンス依存アルゴリズムは、ベストとセカンドベストのアーム間のギャップで「容易」な問題のパフォーマンスを向上させる。
我々は、インスタンス依存の後悔境界を得るのに十分かつ必要である複雑性尺度のファミリーを導入する。
次に、可能な限りギャップに適応する新しいオラクル効率アルゴリズムを導入し、最悪の場合にはミニマックスレートを得る。
論文 参考訳(メタデータ) (2020-10-07T01:33:06Z) - SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep
Reinforcement Learning [102.78958681141577]
SUNRISEは単純な統一アンサンブル法であり、様々な非政治的な深層強化学習アルゴリズムと互換性がある。
SUNRISEは, (a) アンサンブルに基づく重み付きベルマンバックアップと, (b) 最上位の自信境界を用いて行動を選択する推論手法を統合し, 効率的な探索を行う。
論文 参考訳(メタデータ) (2020-07-09T17:08:44Z) - Corruption-robust exploration in episodic reinforcement learning [76.19192549843727]
本研究は, システムにおける報酬と遷移確率の両面において, 敵対的腐敗下での多段階・多段階・多段階強化学習について検討した。
我々の枠組みは、汚職の欠如をほぼ最適に後悔する効率的なアルゴリズムをもたらす。
特に,本研究は,根本的強化学習のためのBandit-Feedbackモデルにおいて,純粋にI.d.遷移からの逸脱を保証した最初のサブ線形後悔の保証を提供する。
論文 参考訳(メタデータ) (2019-11-20T03:49:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。