論文の概要: Thompson Sampling for Combinatorial Semi-bandits with Sleeping Arms and
Long-Term Fairness Constraints
- arxiv url: http://arxiv.org/abs/2005.06725v1
- Date: Thu, 14 May 2020 05:24:53 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-03 04:20:14.763967
- Title: Thompson Sampling for Combinatorial Semi-bandits with Sleeping Arms and
Long-Term Fairness Constraints
- Title（参考訳）: 睡眠アームと長期フェアネス制約を有する組合せ半バンドのトンプソンサンプリング
- Authors: Zhiming Huang, Yifan Xu, Bingshan Hu, Qipeng Wang, Jianping Pan
- Abstract要約: 長時間の公平性制約(CSMAB-F)を用いた睡眠型マルチアーム半帯域問題について検討する。
本研究では,ベータ前のemphTSアルゴリズムとCSMAB-F(TSCSF-B)のベルヌーイ確率を設計する。
- 参考スコア（独自算出の注目度）: 11.907809032205941
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the combinatorial sleeping multi-armed semi-bandit problem with
long-term fairness constraints~(CSMAB-F). To address the problem, we adopt
Thompson Sampling~(TS) to maximize the total rewards and use virtual queue
techniques to handle the fairness constraints, and design an algorithm called
\emph{TS with beta priors and Bernoulli likelihoods for CSMAB-F~(TSCSF-B)}.
Further, we prove TSCSF-B can satisfy the fairness constraints, and the
time-averaged regret is upper bounded by $\frac{N}{2\eta} +
O\left(\frac{\sqrt{mNT\ln T}}{T}\right)$, where $N$ is the total number of
arms, $m$ is the maximum number of arms that can be pulled simultaneously in
each round~(the cardinality constraint) and $\eta$ is the parameter trading off
fairness for rewards. By relaxing the fairness constraints (i.e., let $\eta
\rightarrow \infty$), the bound boils down to the first problem-independent
bound of TS algorithms for combinatorial sleeping multi-armed semi-bandit
problems. Finally, we perform numerical experiments and use a high-rating movie
recommendation application to show the effectiveness and efficiency of the
proposed algorithm.
- Abstract（参考訳）: 長期フェアネス制約(csmab-f)を満たした組合せ睡眠型マルチアーム半バンド問題について検討した。
この問題に対処するために、Thompson Sampling~(TS)を用いて、全報酬を最大化し、仮想キュー技術を用いてフェアネス制約を処理し、CSMAB-F~(TSCSF-B)}のベータ前処理とベルヌーイ確率を持つ「emph{TS」と呼ばれるアルゴリズムを設計する。
さらに、TSCSF-Bがフェアネス制約を満たすことを証明し、平均的後悔は、$\frac{N}{2\eta} + O\left(\frac{\sqrt{mNT\ln T}}{T}\right)$、$N$は武器の総数、$m$は各ラウンドで同時に引くことができる武器の最大数、$\eta$は報酬のフェアネスを取引するパラメータである。
公正性制約(すなわち$\eta \rightarrow \infty$)を緩和することにより、結合は、組合せ型睡眠型半バンドイット問題に対する最初の問題非依存なTSアルゴリズムの有界化へと導かれる。
最後に, 数値実験を行い, 提案アルゴリズムの有効性と効率を示すために, 高評価映画推薦アプリケーションを用いた。
関連論文リスト
- Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Combinatorial Bandits for Maximum Value Reward Function under Max
Value-Index Feedback [9.771002043127728]
本稿では,最大値報酬関数に対する最大値と指数フィードバックに基づくマルチアームバンディット問題を考察する。
有限なサポートを持つ任意の分布にしたがって、アーム結果を持つ問題インスタンスに対して、アルゴリズムを提案し、後悔の束縛を与える。
我々のアルゴリズムは、$O(((k/Delta)log(T))$ distribution-dependent と $tildeO(sqrtT)$ distribution-independent regret を達成する。
論文 参考訳（メタデータ） (2023-05-25T14:02:12Z) - Two-sided Competing Matching Recommendation Markets With Quota and Complementary Preferences Constraints [13.069703665055084]
本稿では,両面のオンラインマッチング市場において,補完的な嗜好とクォータ制約を伴う問題に対処する新しい推奨アルゴリズムを提案する。
混合クォータと相補的な選好制約の存在は、マッチングプロセスの不安定性を引き起こす。
バンドレート学習の枠組みとしてこの問題を定式化し,マルチエージェント多型トンプソンサンプリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-24T18:54:29Z) - Finite-Time Regret of Thompson Sampling Algorithms for Exponential
Family Multi-Armed Bandits [88.21288104408556]
本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。
最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
論文 参考訳（メタデータ） (2022-06-07T18:08:21Z) - Sleeping Combinatorial Bandits [15.004764451770441]
睡眠帯域設定においてよく知られたCUCBアルゴリズムを適用し,それをCSUCBと呼ぶ。
穏やかな条件下では、CSUCBアルゴリズムが$O(sqrtT log (T)$ instance-dependent regret guaranteeを達成することを証明します。
我々の結果は極めて一般的なものであり、非付加的な報酬関数、揮発性アームの可用性、引くべきベースアームの変動数など、実用的な応用によって生じる一般的な環境下で維持されます。
論文 参考訳（メタデータ） (2021-06-03T06:49:44Z) - Combinatorial Bandits without Total Order for Arms [52.93972547896022]
セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。
我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
論文 参考訳（メタデータ） (2021-03-03T23:08:59Z) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳（メタデータ） (2021-02-15T19:10:52Z) - 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) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Thompson Sampling for Linearly Constrained Bandits [18.477962150017095]
我々はLinConTSについて述べる。LinConTSは、各ラウンドで報酬を得る確率に線形制約を課すバンディットのアルゴリズムである。
また,LinConTSでは,過度な制約違反と累積的制約違反はO(log T)で上限づけられていることを示す。
論文 参考訳（メタデータ） (2020-04-20T13:06:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。