論文の概要: Stochastic Bandits with Linear Constraints
- arxiv url: http://arxiv.org/abs/2006.10185v1
- Date: Wed, 17 Jun 2020 22:32:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-19 20:01:35.358511
- Title: Stochastic Bandits with Linear Constraints
- Title（参考訳）: 線形制約付き確率帯域
- Authors: Aldo Pacchiano, Mohammad Ghavamzadeh, Peter Bartlett, Heinrich Jiang
- Abstract要約: 制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 69.757694218456
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a constrained contextual linear bandit setting, where the goal of
the agent is to produce a sequence of policies, whose expected cumulative
reward over the course of $T$ rounds is maximum, and each has an expected cost
below a certain threshold $\tau$. We propose an upper-confidence bound
algorithm for this problem, called optimistic pessimistic linear bandit (OPLB),
and prove an $\widetilde{\mathcal{O}}(\frac{d\sqrt{T}}{\tau-c_0})$ bound on its
$T$-round regret, where the denominator is the difference between the
constraint threshold and the cost of a known feasible action. We further
specialize our results to multi-armed bandits and propose a computationally
efficient algorithm for this setting. We prove a regret bound of
$\widetilde{\mathcal{O}}(\frac{\sqrt{KT}}{\tau - c_0})$ for this algorithm in
$K$-armed bandits, which is a $\sqrt{K}$ improvement over the regret bound we
obtain by simply casting multi-armed bandits as an instance of contextual
linear bandits and using the regret bound of OPLB. We also prove a lower-bound
for the problem studied in the paper and provide simulations to validate our
theoretical results.
- Abstract（参考訳）: 条件付き線形バンディットの設定について検討し、エージェントの目標は一連のポリシーを作ることであり、そこでは、t$ ラウンドの累積報酬が最大であり、それぞれが一定のしきい値である$\tau$ を下回る期待コストを持つ。
この問題に対して,楽観的悲観的線形バンドリット(OPLB)と呼ばれる上限有界アルゴリズムを提案し,そのT$ラウンドの後悔に対して$\widetilde{\mathcal{O}}(\frac{d\sqrt{T}}{\tau-c_0})$を証明した。
さらに,本手法を多腕バンディットに応用し,計算効率の高いアルゴリズムを提案する。
我々は、このアルゴリズムに対する$k$-armed banditsにおける$\widetilde{\mathcal{o}}(\frac{\sqrt{kt}}{\tau - c_0})$の後悔境界を証明した。
また,本論文で研究した問題に対して下限を証明し,理論結果を検証するためのシミュレーションを提供する。
関連論文リスト
- Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds [1.03590082373586]
本稿では,線形帯域探索アルゴリズムTRAiLの提案と解析を行う。
TraiLは、設計(回帰器)行列の最小固有値によって測定された推論品質の$Omega(sqrtT)$成長を保証する。
我々は,期待された後悔に対して,任意のアルゴリズムに対して$Omega(sqrtT)$ minimax小境界を特徴付ける。
論文 参考訳（メタデータ） (2024-11-19T01:08:13Z) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual
Bandits [30.337826346496385]
本稿では、損失ベクトルを全対角に選択し、ラウンドごとのアクションセットを固定分布から引き出す対角線形境界帯域問題について考察する。
この問題の既存の方法は、自由な文脈を生成するためにシミュレータへのアクセスを必要とするか、準最適後悔を達成するか、あるいは計算的に非効率である。
シミュレーションを使わずに$widetildeO(sqrtT)$を後悔して、各ラウンドで設定したアクションが小さい場合に計算効率を維持することで、これらの結果を大幅に改善する。
論文 参考訳（メタデータ） (2023-09-02T03:49:05Z) - Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。
我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
論文 参考訳（メタデータ） (2023-04-25T09:31:20Z) - Squeeze All: Novel Estimator and Self-Normalized Bound for Linear
Contextual Bandits [18.971564419292893]
我々は、$O(sqrtdTlog T)$ regret boundで、$d$は文脈の次元、$T$は時間地平線であるような線形文脈的帯域幅アルゴリズムを提案する。
提案アルゴリズムは,探索を明示的ランダム化により埋め込んだ新しい推定器を備える。
論文 参考訳（メタデータ） (2022-06-11T02:43:17Z) - Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。
我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。
我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
論文 参考訳（メタデータ） (2022-04-24T03:10:27Z) - Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。
我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
論文 参考訳（メタデータ） (2022-03-29T15:27:13Z) - Impact of Representation Learning in Linear Bandits [83.17684841392754]
本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。
我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-13T16:35:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。