論文の概要: When Combinatorial Thompson Sampling meets Approximation Regret
- arxiv url: http://arxiv.org/abs/2302.11182v1
- Date: Wed, 22 Feb 2023 07:27:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-23 16:09:07.195692
- Title: When Combinatorial Thompson Sampling meets Approximation Regret
- Title（参考訳）: Combinatorial Thompson Smplingが近似レパートメントに出会ったとき
- Authors: Pierre Perrault
- Abstract要約: マルチアームバンディット問題(CMAB)に対するコンビニアルトンプソンサンプリングポリシー(CTS)について検討する。
近似オラクルの特定の条件下で得られた CTS に対して,最初の $mathcalO(log(T)/Delta)$ approximation regret upperbound を提供する。
- 参考スコア（独自算出の注目度）: 7.538482310185135
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the Combinatorial Thompson Sampling policy (CTS) for combinatorial
multi-armed bandit problems (CMAB), within an approximation regret setting.
Although CTS has attracted a lot of interest, it has a drawback that other
usual CMAB policies do not have when considering non-exact oracles: for some
oracles, CTS has a poor approximation regret (scaling linearly with the time
horizon $T$) [Wang and Chen, 2018]. A study is then necessary to discriminate
the oracles on which CTS could learn. This study was started by Kong et al.
[2021]: they gave the first approximation regret analysis of CTS for the greedy
oracle, obtaining an upper bound of order $\mathcal{O}(\log(T)/\Delta^2)$,
where $\Delta$ is some minimal reward gap. In this paper, our objective is to
push this study further than the simple case of the greedy oracle. We provide
the first $\mathcal{O}(\log(T)/\Delta)$ approximation regret upper bound for
CTS, obtained under a specific condition on the approximation oracle, allowing
a reduction to the exact oracle analysis. We thus term this condition
REDUCE2EXACT, and observe that it is satisfied in many concrete examples.
Moreover, it can be extended to the probabilistically triggered arms setting,
thus capturing even more problems, such as online influence maximization.
- Abstract（参考訳）: 我々は,多腕バンディット問題(cmab)に対する組合せトンプソンサンプリングポリシー(cts)を近似後悔設定で検討した。
ctsには多くの関心が寄せられているが、他のcmabポリシーは、非実効的なオラクルを考えるときに持っていないという欠点がある: いくつかのオラクルにとって、ctsは、(time horizon $t$で線形にスケールする)近似的な後悔が乏しい[wang and chen, 2018]。
CTSが学べるオラクルを識別するためには、研究が必要である。
この研究はKongらによって始められた。
[2021]: 彼らはグリーディオラクルに対するCTSの最初の近似的後悔解析を行い、位数$\mathcal{O}(\log(T)/\Delta^2)$の上限を得る。
本研究の目的は,本研究を強欲なオラクルの単純な場合よりも進めることである。
我々は、近似オラクルの特定の条件の下で得られた CTS に対して、最初の $\mathcal{O}(\log(T)/\Delta)$ approximation regret upperbound を提供する。
そこで我々は,この条件をREDUCE2EXACTと呼び,多くの具体例で満足していることを確認する。
さらに、確率的に引き起こされる腕の設定に拡張することができ、オンラインの影響最大化のようなさらに多くの問題を捉えることができる。
関連論文リスト
- Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
乗算重み更新などの既存の学習アルゴリズムが最適に近いことを示す。
結果はKothari と Mehta が提案したアルゴリズムの枠組みで得られた。
論文 参考訳（メタデータ） (2024-11-04T00:39:52Z) - Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
我々は、ほぼ最適の$T$-sparse CCEの計算限界を低く証明する。
特に,最大傾斜角の不適応性は,時間内に非自明な間隔を達成できないことを示す。
論文 参考訳（メタデータ） (2024-11-04T00:34:56Z) - Langevin Thompson Sampling with Logarithmic Communication: Bandits and
Reinforcement Learning [34.4255062106615]
トンプソンサンプリング(TS)は、使用が容易で、経験的性能に訴えるため、シーケンシャルな意思決定に広く用いられている。
バッチ化された$textitLangevin Thompson Sampling$アルゴリズムを提案する。
アルゴリズムは計算効率が高く,MABでは$mathcalO(log T)$,RLでは$mathcalO(sqrtT)$と同じオーダー最適後悔保証を維持している。
論文 参考訳（メタデータ） (2023-06-15T01:16:29Z) - Discounted Thompson Sampling for Non-Stationary Bandit Problems [13.656518163592349]
NS-MAB(Non-stationary multi-armed bandit)問題も最近注目されている。
非定常条件の両方に対処するため,ガウシアン先行値を用いたディスカウントトンプソンサンプリング(DS-TS)を提案する。
我々のアルゴリズムは、トンプソンサンプリングに割引係数を組み込むことにより、変化に順応的に適応する。
論文 参考訳（メタデータ） (2023-05-18T05:29:52Z) - Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
本稿では, 難易度の高い環境下での強化学習(RL)の基本的限界について検討する。
Emphmulti-steping POMDPs に対して、潜伏状態空間依存はサンプル複雑性において少なくとも$Omega(S1.5)$であることを示す。
論文 参考訳（メタデータ） (2023-02-02T18:59:30Z) - Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。
まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。
次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-31T13:09:39Z) - The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret
and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。
一般関数クラスと一般モデルクラスで学ぶことに集中する。
対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文 参考訳（メタデータ） (2022-03-03T02:55:55Z) - First-Order Regret in Reinforcement Learning with Linear Function
Approximation: A Robust Estimation Approach [57.570201404222935]
我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。
この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
論文 参考訳（メタデータ） (2021-12-07T00:29:57Z) - The Hardness Analysis of Thompson Sampling for Combinatorial
Semi-bandits with Greedy Oracle [16.50998008977657]
トンプソンサンプリング(TS)は、バンディット地域に多くの関心を集めている。
1930年代に導入されたが、理論上は近年まで証明されていない。
論文 参考訳（メタデータ） (2021-11-08T06:40:03Z) - Thompson Sampling for Linearly Constrained Bandits [18.477962150017095]
我々はLinConTSについて述べる。LinConTSは、各ラウンドで報酬を得る確率に線形制約を課すバンディットのアルゴリズムである。
また,LinConTSでは,過度な制約違反と累積的制約違反はO(log T)で上限づけられていることを示す。
論文 参考訳（メタデータ） (2020-04-20T13:06:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。