論文の概要: Combinatorial Logistic Bandits
- arxiv url: http://arxiv.org/abs/2410.17075v2
- Date: Tue, 19 Nov 2024 15:50:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-20 13:33:18.782221
- Title: Combinatorial Logistic Bandits
- Title（参考訳）: Combinatorのロジスティックバンド
- Authors: Xutong Liu, Xiangxiang Dai, Xuchuang Wang, Mohammad Hajiesmaili, John C. S. Lui,
- Abstract要約: 我々はロジスティック・バンディット(CLogB)と呼ばれる新しいフレームワークを紹介する。
各ラウンドでは、ベースアームのサブセット(スーパーアームと呼ばれる)が選択され、各ベースアームの結果はバイナリとなる。
実世界のデータセットの実験では、ベンチマークアルゴリズムと比較してアルゴリズムの性能が優れていた。
- 参考スコア（独自算出の注目度）: 30.829239785016934
- License:
- Abstract: We introduce a novel framework called combinatorial logistic bandits (CLogB), where in each round, a subset of base arms (called the super arm) is selected, with the outcome of each base arm being binary and its expectation following a logistic parametric model. The feedback is governed by a general arm triggering process. Our study covers CLogB with reward functions satisfying two smoothness conditions, capturing application scenarios such as online content delivery, online learning to rank, and dynamic channel allocation. We first propose a simple yet efficient algorithm, CLogUCB, utilizing a variance-agnostic exploration bonus. Under the 1-norm triggering probability modulated (TPM) smoothness condition, CLogUCB achieves a regret bound of $\tilde{O}(d\sqrt{\kappa KT})$, where $\tilde{O}$ ignores logarithmic factors, $d$ is the dimension of the feature vector, $\kappa$ represents the nonlinearity of the logistic model, and $K$ is the maximum number of base arms a super arm can trigger. This result improves on prior work by a factor of $\tilde{O}(\sqrt{\kappa})$. We then enhance CLogUCB with a variance-adaptive version, VA-CLogUCB, which attains a regret bound of $\tilde{O}(d\sqrt{KT})$ under the same 1-norm TPM condition, improving another $\tilde{O}(\sqrt{\kappa})$ factor. VA-CLogUCB shows even greater promise under the stronger triggering probability and variance modulated (TPVM) condition, achieving a leading $\tilde{O}(d\sqrt{T})$ regret, thus removing the additional dependency on the action-size $K$. Furthermore, we enhance the computational efficiency of VA-CLogUCB by eliminating the nonconvex optimization process when the context feature map is time-invariant while maintaining the tight $\tilde{O}(d\sqrt{T})$ regret. Finally, experiments on synthetic and real-world datasets demonstrate the superior performance of our algorithms compared to benchmark algorithms.
- Abstract（参考訳）: 本稿では,各ラウンドにおいて,各ベースアームのサブセット(スーパーアームと呼ばれる)が選択され,各ベースアームがバイナリとなり,ロジスティックパラメトリックモデルにより期待される新しいフレームワークCLogBを紹介する。
フィードバックは、一般的なアームトリガープロセスによって管理される。
本研究は,2つのスムーズな条件を満たす報酬関数を持つCLogBについて,オンラインコンテンツ配信,ランク付けのためのオンライン学習,動的チャネル割り当てなどのアプリケーションシナリオを抽出する。
まず、分散に依存しない探索ボーナスを利用した、単純で効率的なアルゴリズムCLogUCBを提案する。
1-ノルムトリガリング確率変調(TPM)の滑らかさ条件の下で、CLogUCBは、$\tilde{O}(d\sqrt{\kappa KT})$, where $\tilde{O}$は対数因子を無視し、$d$は特徴ベクトルの次元であり、$\kappa$はロジスティックモデルの非線形性を表し、$K$はスーパーアームが引き起こすベースアームの最大数である。
この結果は、$\tilde{O}(\sqrt{\kappa})$ の係数で以前の作業を改善する。
次に、CLogUCB を分散適応バージョン VA-CLogUCB で拡張し、同じ 1-ノルムの TPM 条件の下で $\tilde{O}(d\sqrt{KT})$ の後悔境界を達成し、別の $\tilde{O}(\sqrt{\kappa})$ 係数を改善した。
VA-CLogUCB はより強いトリガー確率と分散変調 (TPVM) 条件の下でさらに大きな公約を示し、先頭の $\tilde{O}(d\sqrt{T})$ regret を達成する。
さらに, VA-CLogUCBの計算効率は, コンテクスト特徴写像が時間不変である場合に非凸最適化プロセスを排除し, タイトな$\tilde{O}(d\sqrt{T})$ regretを維持することで向上する。
最後に、合成および実世界のデータセットに関する実験は、ベンチマークアルゴリズムと比較してアルゴリズムの優れた性能を示す。
関連論文リスト
- Provably Efficient High-Dimensional Bandit Learning with Batched
Feedbacks [93.00280593719513]
本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。
具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。
我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
論文 参考訳（メタデータ） (2023-11-22T06:06:54Z) - Federated Linear Bandits with Finite Adversarial Actions [20.1041278044797]
我々は、M$のクライアントが中央サーバと通信し、線形文脈の帯域幅問題を解決するための連合線形帯域幅モデルについて検討する。
逆有限作用集合のユニークな問題に対処するため、FedSupLinUCBアルゴリズムを提案する。
我々は、FedSupLinUCBが$tildeO(sqrtd T)$の完全後悔を達成したことを証明している。
論文 参考訳（メタデータ） (2023-11-02T03:41:58Z) - Sharper Model-free Reinforcement Learning for Average-reward Markov
Decision Processes [21.77276136591518]
我々はマルコフ決定過程(MDPs)のための証明可能なモデルフリー強化学習(RL)アルゴリズムを開発した。
シミュレータ設定では,$widetildeO left(fracSAmathrmsp(h*)epsilon2+fracS2Amathrmsp(h*)epsilon2right)$サンプルを用いて,$epsilon$-optimal Policyを求める。
論文 参考訳（メタデータ） (2023-06-28T17:43:19Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [45.305256056479045]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳（メタデータ） (2022-10-15T09:22:22Z) - Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with
Probabilistically Triggered Arms or Independent Arms [53.89752069984382]
半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。
まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。
次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-31T13:09:39Z) - Contextual Combinatorial Volatile Bandits via Gaussian Processes [10.312968200748116]
利用可能なベースアームのセットとそのコンテキストによるコンテキスト的バンディット問題を考える。
我々は,カーネル上信頼境界(O'CLOK-UCB)を用いた最適組合せ学習と最適化というアルゴリズムを提案する。
両アルゴリズムが従来のUTBベースのアルゴリズムを現実的な設定で大幅に上回っていることを実験的に示す。
論文 参考訳（メタデータ） (2021-10-05T18:02:10Z) - 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) - Provably Efficient Reinforcement Learning with Linear Function
Approximation Under Adaptivity Constraints [94.76881135901753]
一般的な限定的適応モデルとして,バッチ学習モデルとレアポリシースイッチモデルがある。
提案したLSVI-UCB-Batchアルゴリズムは,$tilde O(sqrtd3H3T + dHT/B)$ regretを実現する。
まれなポリシスイッチモデルでは,提案されたLSVI-UCB-RareSwitchアルゴリズムは,$tilde O(sqrtd3H3T[1+T/(dH)]dH/B)$の後悔を享受する。
論文 参考訳（メタデータ） (2021-01-06T18:56:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。