論文の概要: Thompson Sampling for Linearly Constrained Bandits
- arxiv url: http://arxiv.org/abs/2004.09258v2
- Date: Tue, 12 May 2020 18:34:47 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-11 17:43:08.960220
- Title: Thompson Sampling for Linearly Constrained Bandits
- Title（参考訳）: 線形拘束帯域に対するトンプソンサンプリング
- Authors: Vidit Saxena, Joseph E. Gonzalez, and Joakim Jald\'en
- Abstract要約: 我々はLinConTSについて述べる。LinConTSは、各ラウンドで報酬を得る確率に線形制約を課すバンディットのアルゴリズムである。
また,LinConTSでは,過度な制約違反と累積的制約違反はO(log T)で上限づけられていることを示す。
- 参考スコア（独自算出の注目度）: 18.477962150017095
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We address multi-armed bandits (MAB) where the objective is to maximize the
cumulative reward under a probabilistic linear constraint. For a few real-world
instances of this problem, constrained extensions of the well-known Thompson
Sampling (TS) heuristic have recently been proposed. However, finite-time
analysis of constrained TS is challenging; as a result, only O(\sqrt{T}) bounds
on the cumulative reward loss (i.e., the regret) are available. In this paper,
we describe LinConTS, a TS-based algorithm for bandits that place a linear
constraint on the probability of earning a reward in every round. We show that
for LinConTS, the regret as well as the cumulative constraint violations are
upper bounded by O(\log T) for the suboptimal arms. We develop a proof
technique that relies on careful analysis of the dual problem and combine it
with recent theoretical work on unconstrained TS. Through numerical experiments
on two real-world datasets, we demonstrate that LinConTS outperforms an
asymptotically optimal upper confidence bound (UCB) scheme in terms of
simultaneously minimizing the regret and the violation.
- Abstract（参考訳）: 本稿では,確率的線形制約の下で累積報酬を最大化することを目的としたマルチアームバンディット (mab) について述べる。
この問題の現実的な例では、よく知られたトンプソンサンプリング(TS)ヒューリスティックの拡張が最近提案されている。
しかし、制約付きTSの有限時間解析は困難であり、結果として、O(\sqrt{T}) のみが累積報酬損失(すなわち後悔)に制限される。
本稿では,各ラウンドの報酬を得る確率に線形制約を課す,バンドイットのtsベースアルゴリズムであるlincontsについて述べる。
また,LinConTSでは,過度な制約違反と累積的制約違反がO(\log T)によって上界されていることを示す。
本稿では,双対問題を慎重に解析し,非制約TSに関する最近の理論的研究と組み合わせた証明手法を開発した。
実世界の2つのデータセットの数値実験により、LinConTSは、後悔と違反を同時に最小化するために、漸近的に最適な上信頼境界(UCB)スキームより優れていることを示した。
関連論文リスト
- Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints [8.784438985280094]
線形制約が未知の多腕バンディットにおける純粋探索として問題を研究する。
まず、制約下での純粋な探索のために、サンプルの複雑さを低く抑えたラグランジアン緩和を提案する。
第二に、ラグランジアンの下界と凸の性質を利用して、トラック・アンド・ストップとガミファイド・エクスプローラー(LATSとLAGEX)の2つの計算効率の良い拡張を提案する。
論文 参考訳（メタデータ） (2024-10-24T15:26:14Z) - Bayesian Bandit Algorithms with Approximate Inference in Stochastic Linear Bandits [21.09844002135398]
我々は,線形トンプソンサンプリング (LinTS) とベイズ的上部信頼境界の拡張 (LinBUCB) が,元の後悔の上界の速度を保てることを示す。
また、LinBUCBはLinTSの後悔率を$tildeO(d3/2sqrtT)$から$tildeO(dsqrtT)$に短縮することを示した。
論文 参考訳（メタデータ） (2024-06-20T07:45:38Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳（メタデータ） (2023-10-02T08:15:52Z) - Thompson Exploration with Best Challenger Rule in Best Arm
Identification [66.33448474838342]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳（メタデータ） (2023-10-01T01:37:02Z) - Optimality of Thompson Sampling with Noninformative Priors for Pareto
Bandits [81.45853204922795]
トンプソンサンプリングは、いくつかの報酬モデルにおいて問題依存の低い境界を達成することが示されている。
重い尾を持つパレートモデルに対するTSの最適性は、2つの未知のパラメータによってパラメータ化される。
ジェフリーズおよび参照先行値を持つTSは、トラルニケート手順を使用すると、下界を達成できる。
論文 参考訳（メタデータ） (2023-02-03T04:47:14Z) - Sample-Then-Optimize Batch Neural Thompson Sampling [50.800944138278474]
我々はトンプソンサンプリング(TS)ポリシーに基づくブラックボックス最適化のための2つのアルゴリズムを提案する。
入力クエリを選択するには、NNをトレーニングし、トレーニングされたNNを最大化してクエリを選択するだけです。
我々のアルゴリズムは、大きなパラメータ行列を逆転する必要性を助長するが、TSポリシーの妥当性は保たれている。
論文 参考訳（メタデータ） (2022-10-13T09:01:58Z) - On Kernelized Multi-Armed Bandits with Constraints [16.102401271318012]
一般に未知の報酬関数と一般未知の制約関数を併用した帯域幅問題について検討する。
本稿では,アルゴリズムの性能解析のための一般的なフレームワークを提案する。
本稿では,数値実験により提案アルゴリズムの優れた性能を示す。
論文 参考訳（メタデータ） (2022-03-29T14:02:03Z) - A Unifying Theory of Thompson Sampling for Continuous Risk-Averse
Bandits [91.3755431537592]
本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。
大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。
リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
論文 参考訳（メタデータ） (2021-08-25T17:09:01Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - On Frequentist Regret of Linear Thompson Sampling [8.071506311915398]
本稿では,決定者側が $mathbbRd$ の時間依存ベクトル集合から行動を選択し,雑音の報奨を受ける線形帯域問題について検討する。
目的は、後悔を最小限に抑えることであり、決定者の累積的な報奨と、各アクションの期待報奨にアクセスできる神託の報奨とを、一連のT$決定に比較して区別することである。
論文 参考訳（メタデータ） (2020-06-11T20:19:41Z) - A General Theory of the Stochastic Linear Bandit and Its Applications [8.071506311915398]
本稿では,線形バンディット問題に対する一般解析フレームワークとアルゴリズム群を紹介する。
予測における最適化という新たな概念は、OFULの過剰探索問題を減少させるSieeved greedy(SG)と呼ばれる新しいアルゴリズムを生み出します。
SGが理論的に最適であることを示すことに加えて、実験シミュレーションにより、SGはgreedy、OFUL、TSといった既存のベンチマークよりも優れていることが示された。
論文 参考訳（メタデータ） (2020-02-12T18:54:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。