論文の概要: A Multi-Arm Bandit Approach To Subset Selection Under Constraints
- arxiv url: http://arxiv.org/abs/2102.04824v1
- Date: Tue, 9 Feb 2021 13:48:57 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-10 23:28:12.331711
- Title: A Multi-Arm Bandit Approach To Subset Selection Under Constraints
- Title（参考訳）: 制約下でのサブセット選択のためのマルチアーム帯域幅アプローチ
- Authors: Ayush Deva, Kumar Abhishek, Sujit Gujar
- Abstract要約: 中央プランナーがエージェントのサブセットを選択する必要がある問題の種類を,それぞれ異なる品質とコストで検討する。
エージェントの品質が分かると、我々は問題を整数線形プログラム(ILP)として定式化する。
ILPの正確な解を提供する決定論的アルゴリズム(dpss)を提案する。
- 参考スコア（独自算出の注目度）: 14.543433698096667
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We explore the class of problems where a central planner needs to select a
subset of agents, each with different quality and cost. The planner wants to
maximize its utility while ensuring that the average quality of the selected
agents is above a certain threshold. When the agents' quality is known, we
formulate our problem as an integer linear program (ILP) and propose a
deterministic algorithm, namely \dpss\ that provides an exact solution to our
ILP.
We then consider the setting when the qualities of the agents are unknown. We
model this as a Multi-Arm Bandit (MAB) problem and propose \newalgo\ to learn
the qualities over multiple rounds. We show that after a certain number of
rounds, $\tau$, \newalgo\ outputs a subset of agents that satisfy the average
quality constraint with a high probability. Next, we provide bounds on $\tau$
and prove that after $\tau$ rounds, the algorithm incurs a regret of $O(\ln
T)$, where $T$ is the total number of rounds. We further illustrate the
efficacy of \newalgo\ through simulations.
To overcome the computational limitations of \dpss, we propose a
polynomial-time greedy algorithm, namely \greedy, that provides an approximate
solution to our ILP. We also compare the performance of \dpss\ and \greedy\
through experiments.
- Abstract（参考訳）: 中央プランナーがエージェントのサブセットを選択する必要がある問題の種類を,それぞれ異なる品質とコストで検討する。
プランナーは、選択したエージェントの平均品質が一定のしきい値を超えていることを保証しながら、そのユーティリティを最大化したいです。
エージェントの品質が分かっているとき、我々はこの問題を整数線形プログラム(ilp)として定式化し、決定論的アルゴリズム、すなわち我々のilpの厳密な解を提供する \dpss\ を提案する。
次に,エージェントの質が不明な場合の設定について考察する。
我々はこれをマルチアームバンドイット(MAB)問題としてモデル化し、複数ラウンドで品質を学習するために「newalgo\」を提案する。
一定の回数のラウンドの後、$\tau$, \newalgo\ は平均品質制約を満たすエージェントのサブセットを高い確率で出力することを示した。
次に、$\tau$ の境界を提供し、$\tau$ ラウンドの後、アルゴリズムは $O(\ln T)$ の後悔を招き、$T$ がラウンド総数であることを証明します。
さらに、シミュレーションを通じて \newalgo\ の有効性を示す。
計算上の制限を克服するために、我々は多項式時間勾配アルゴリズムである \greedy を提案し、このアルゴリズムは ILP に近似解を提供する。
また、実験を通じて \dpss\ と \greedy\ のパフォーマンスを比較する。
関連論文リスト
- Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space [0.0]
離散時間可算状態空間マルコフ決定過程の族を最適に制御する問題について検討する。
動的サイズのエピソードを用いたトンプソンサンプリングに基づくアルゴリズムを提案する。
提案アルゴリズムは, 近似最適制御アルゴリズムの開発に応用可能であることを示す。
論文 参考訳（メタデータ） (2023-06-05T03:57:16Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。
提案アルゴリズムは,レコメンデーションシステムや交通機関などの分野に適用可能である。
論文 参考訳（メタデータ） (2023-01-31T03:49:00Z) - Distributed Contextual Linear Bandits with Minimax Optimal Communication
Cost [48.288452411283444]
そこでは,$N$エージェントが協調して,$d$次元の特徴を持つ線形帯域最適化問題を解く。
本稿では,LinUCBアルゴリズムの分散バッチ除去版であるDisBE-LUCBを提案する。
我々は、DisBE-LUCBの通信コストがわずか$tildemathcalO(dN)$であり、その後悔は少なくとも$tildemathcalO(dN)$であることを示す。
論文 参考訳（メタデータ） (2022-05-26T05:56:23Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Fully Gap-Dependent Bounds for Multinomial Logit Bandit [5.132017939561661]
マルチノミアルロジット (MNL) バンディット問題について検討し、各ステップごとに、販売者は、N$アイテムのプールから最大でK$のサイズを提供する。
i) $widetildeO(sum_i = 1N Delta_i-2)$ time steps with high probability, (ii) $O(sum_i notin S* KDelta_i)というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-11-19T17:52:12Z) - Thompson sampling for linear quadratic mean-field teams [3.957353452014781]
エージェント間で動的およびコストが結合される未知のマルチエージェント線形二次系(LQ)の最適制御について検討する。
我々は,システムモデルの構造を活かした新しいトンプソンサンプリング学習アルゴリズムを提案し,時間軸に異なる種類のエージェントを持つシステムに対してベイズが提案したアルゴリズムを,エージェントの総数に関係なく$T$ is $tildemathcalO big( |M|1.5 sqrtT big)$で後悔していることを示す。
論文 参考訳（メタデータ） (2020-11-09T19:07:32Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
基本アルゴリズムを選択できるメタアルゴリズムを開発した。
基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
論文 参考訳（メタデータ） (2020-03-03T18:46:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。