論文の概要: Multi-armed Bandits with Cost Subsidy
- arxiv url: http://arxiv.org/abs/2011.01488v3
- Date: Mon, 15 Mar 2021 11:49:38 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-30 03:59:18.213929
- Title: Multi-armed Bandits with Cost Subsidy
- Title(参考訳): 費用補助付きマルチアームバンド
- Authors: Deeksha Sinha, Karthik Abinav Sankararama, Abbas Kazerouni, Vashist
Avadhanula
- Abstract要約: 本稿では、インテリジェントSMSルーティング問題と広告オーディエンス最適化問題という2つのアプリケーションを提案する。
既存のMABアルゴリズムの素早い一般化は、この問題に対してうまく機能しないことを示す。
また,このアルゴリズムに対して,探索定理の簡単な変種を提示し,ほぼ最適な後悔境界を定めている。
- 参考スコア(独自算出の注目度): 1.6631602844999724
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we consider a novel variant of the multi-armed bandit (MAB)
problem, MAB with cost subsidy, which models many real-life applications where
the learning agent has to pay to select an arm and is concerned about
optimizing cumulative costs and rewards. We present two applications,
intelligent SMS routing problem and ad audience optimization problem faced by
several businesses (especially online platforms), and show how our problem
uniquely captures key features of these applications. We show that naive
generalizations of existing MAB algorithms like Upper Confidence Bound and
Thompson Sampling do not perform well for this problem. We then establish a
fundamental lower bound on the performance of any online learning algorithm for
this problem, highlighting the hardness of our problem in comparison to the
classical MAB problem. We also present a simple variant of explore-then-commit
and establish near-optimal regret bounds for this algorithm. Lastly, we perform
extensive numerical simulations to understand the behavior of a suite of
algorithms for various instances and recommend a practical guide to employ
different algorithms.
- Abstract(参考訳): 本稿では,マルチアーム・バンディット(MAB)問題(MAB)の新たな変種として,学習エージェントがアームの選択に支払わなければならない多くの実生活応用をモデル化し,累積コストと報酬の最適化を懸念するコスト補助付きMABについて考察する。
我々は,複数の企業(特にオンラインプラットフォーム)が直面する,インテリジェントなsmsルーティング問題と広告オーディエンス最適化問題という2つのアプリケーションを提示する。
上信頼境界やトンプソンサンプリングのような既存のMABアルゴリズムの素早い一般化はこの問題に対してうまく機能しないことを示す。
次に,本問題に対するオンライン学習アルゴリズムの性能に関する基礎的下限を定め,古典的mab問題と比較して,問題の難易度を強調する。
また,このアルゴリズムに対して,探索定理の簡単な変種を提示し,ほぼ最適な後悔境界を確立する。
最後に,様々なインスタンスに対するアルゴリズムの組の挙動を理解するために,広範な数値シミュレーションを行い,異なるアルゴリズムを利用するための実践的ガイドを推薦する。
関連論文リスト
- Improving Thompson Sampling via Information Relaxation for Budgeted Multi-armed Bandits [1.4732811715354452]
我々は、各アームが選択時に異なるリソースを消費する、$Kの武器付きバンディット問題を考える。
我々はトンプソンサンプリングのようにランダム化される一連のアルゴリズムを提案するが、予算制約に関してより慎重に決定を最適化する。
論文 参考訳(メタデータ) (2024-08-28T04:56:06Z) - A Federated Online Restless Bandit Framework for Cooperative Resource Allocation [23.698976872351576]
MRPの未知系力学を用いた協調資源配分問題について検討する。
我々は、このマルチエージェントオンラインRMAB問題を解決するために、フェデレートトンプソン対応Whittle Index(FedTSWI)アルゴリズムを作成した。
数値計算の結果,提案アルゴリズムは,ベースラインと比較して,$mathcalO(sqrtTlog(T))$の高速収束率と性能の向上を実現している。
論文 参考訳(メタデータ) (2024-06-12T08:34:53Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳(メタデータ) (2023-10-08T23:39:38Z) - Stochastic Rising Bandits [40.32303434592863]
本研究は、腕が単調に非減少している、安静時および安静時バンディットの特定の症例について検討する。
この特性により、ペイオフの規則性を利用して、厳密な後悔の限界を提供する、特別に構築されたアルゴリズムを設計することができる。
我々は,本アルゴリズムを実世界のデータセットに対するオンラインモデル選択問題や,複数の合成されたタスクに対する非定常MABの最先端手法と経験的に比較した。
論文 参考訳(メタデータ) (2022-12-07T17:30:45Z) - Softmax with Regularization: Better Value Estimation in Multi-Agent
Reinforcement Learning [72.28520951105207]
q$-learningの過大評価は、シングルエージェント強化学習で広く研究されている重要な問題である。
ベースラインから逸脱する大きな関節動作値をペナライズする,新たな正規化ベースの更新方式を提案する。
本手法は,StarCraft IIマイクロマネジメントの課題に対して,一貫した性能向上を実現する。
論文 参考訳(メタデータ) (2021-03-22T14:18:39Z) - Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
バンディットアルゴリズムを結合する簡単な手法を提案する。
私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
論文 参考訳(メタデータ) (2020-12-24T05:36:29Z) - Constrained Multiagent Rollout and Multidimensional Assignment with the
Auction Algorithm [0.0]
本稿では,制約付き決定論的動的プログラミングに適用可能なロールアウトアルゴリズムの拡張について考察する。
提案手法では,ベースが実現可能な解を生成する場合,ロールアウトアルゴリズムはコスト改善特性を有することを示す。
コスト改善特性は計算要求を大幅に削減した代替実装で維持されていることを示す。
論文 参考訳(メタデータ) (2020-02-18T07:09:06Z) - GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal
Black Box Constraint Satisfaction [69.94831587339539]
本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。
我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
論文 参考訳(メタデータ) (2020-02-17T20:21:20Z) - Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。
我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。
我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
論文 参考訳(メタデータ) (2020-02-01T15:33:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。