論文の概要: Stage-wise Conservative Linear Bandits
- arxiv url: http://arxiv.org/abs/2010.00081v1
- Date: Wed, 30 Sep 2020 19:51:37 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-12 22:26:16.696496
- Title: Stage-wise Conservative Linear Bandits
- Title(参考訳): ステージワイズ保存リニアバンディット
- Authors: Ahmadreza Moradipari, Christos Thrampoulidis, Mahnoosh Alizadeh
- Abstract要約: オンライン広告や医療実験などのアプリケーションに現れる(未知の)安全制約を考慮に入れた帯域最適化について検討する。
ベースライン制約を尊重し、順序 O(sqrtT log T) の確率的後悔境界を楽しむ2つの新しいアルゴリズムを提案する。
特に、提案アルゴリズムは、様々な問題に対処するために、小さな修正だけで調整できる。
- 参考スコア(独自算出の注目度): 37.717532659194426
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study stage-wise conservative linear stochastic bandits: an instance of
bandit optimization, which accounts for (unknown) safety constraints that
appear in applications such as online advertising and medical trials. At each
stage, the learner must choose actions that not only maximize cumulative reward
across the entire time horizon but further satisfy a linear baseline constraint
that takes the form of a lower bound on the instantaneous reward. For this
problem, we present two novel algorithms, stage-wise conservative linear
Thompson Sampling (SCLTS) and stage-wise conservative linear UCB (SCLUCB), that
respect the baseline constraints and enjoy probabilistic regret bounds of order
O(\sqrt{T} \log^{3/2}T) and O(\sqrt{T} \log T), respectively. Notably, the
proposed algorithms can be adjusted with only minor modifications to tackle
different problem variations, such as constraints with bandit-feedback, or an
unknown sequence of baseline actions. We discuss these and other improvements
over the state-of-the-art. For instance, compared to existing solutions, we
show that SCLTS plays the (non-optimal) baseline action at most O(\log{T})
times (compared to O(\sqrt{T})). Finally, we make connections to another
studied form of safety constraints that takes the form of an upper bound on the
instantaneous reward. While this incurs additional complexity to the learning
process as the optimal action is not guaranteed to belong to the safe set at
each round, we show that SCLUCB can properly adjust in this setting via a
simple modification.
- Abstract(参考訳): 段階的に保守的な線形確率的包帯について検討する: オンライン広告や医療裁判などのアプリケーションに現れる(未知の)安全制約を考慮した帯域最適化の例である。
各段階では、学習者は累積報酬を時間軸全体にわたって最大化するだけでなく、瞬時報酬の下のバウンドの形をとる線形ベースライン制約を満たすアクションを選択する必要がある。
この問題に対して、次数 O(\sqrt{T} \log^{3/2}T) と O(\sqrt{T} \log T) の確率的後悔境界をそれぞれ楽しむ2つの新しいアルゴリズム、Stage-wise conservative linear Thompson Smpling (SCLTS) とStage-wise conservative linear UCB (SCLUCB) を提案する。
特に,提案アルゴリズムは,Bandit-feedbackの制約や未知のベースライン動作といった,様々な問題に対処するための小さな修正のみで調整することができる。
最先端技術に対するこれらの改善について論じる。
例えば、既存の解と比較して、SCLTS が O(\log{T}) の時間(O(\sqrt{T}) と比較)で(最適でない)ベースラインの作用をすることを示す。
最後に、私たちは、即時報酬の上限の形式を取る、他の研究された安全制約形式につながります。
最適動作が各ラウンドの安全セットに属することが保証されていないため、学習プロセスにさらなる複雑さが生じるが、SCLUCBはこの設定を簡単な修正によって適切に調整できることを示す。
関連論文リスト
- Pure Exploration in Bandits with Linear Constraints [15.547603114649464]
マルチアーム・バンディット・セットアップにおいて、最適ポリシーを一定の信頼度で識別する問題に対処する。
この設定に最適な2つのアルゴリズムを導入する。1つはトラック・アンド・ストップ法であり、もう1つはゲーム理論に基づく手法である。
限界を検証し、制約が問題の硬さをどのように変えるかを視覚化する実験結果を提供する。
論文 参考訳(メタデータ) (2023-06-22T10:00:33Z) - PopArt: Efficient Sparse Regression and Experimental Design for Optimal
Sparse Linear Bandits [29.097522376094624]
そこで我々はPopArtと呼ばれる単純で効率的なスパース線形推定法を提案する。
我々は, 粗い線形バンディットアルゴリズムを導出し, 美術品の状態に対する後悔の上界の改善を享受する。
論文 参考訳(メタデータ) (2022-10-25T19:13:20Z) - Interactively Learning Preference Constraints in Linear Bandits [100.78514640066565]
我々は、既知の報酬と未知の制約で逐次意思決定を研究する。
応用として,運転シミュレーションにおいて,人間の嗜好を表現するための学習制約を検討する。
論文 参考訳(メタデータ) (2022-06-10T17:52:58Z) - Stochastic Conservative Contextual Linear Bandits [8.684768561839146]
不確実性の下での安全なリアルタイム意思決定の問題について検討する。
我々は、リアルタイム意思決定のための保守的な文脈的帯域幅の定式化を定式化する。
論文 参考訳(メタデータ) (2022-03-29T14:50:50Z) - On Kernelized Multi-Armed Bandits with Constraints [16.102401271318012]
一般に未知の報酬関数と一般未知の制約関数を併用した帯域幅問題について検討する。
本稿では,アルゴリズムの性能解析のための一般的なフレームワークを提案する。
本稿では,数値実験により提案アルゴリズムの優れた性能を示す。
論文 参考訳(メタデータ) (2022-03-29T14:02:03Z) - Nearly Dimension-Independent Sparse Linear Bandit over Small Action
Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。
この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。
本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文 参考訳(メタデータ) (2020-09-04T04:10:39Z) - On Lower Bounds for Standard and Robust Gaussian Process Bandit
Optimization [55.937424268654645]
有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。
本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
論文 参考訳(メタデータ) (2020-08-20T03:48:14Z) - 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) - Improved Algorithms for Conservative Exploration in Bandits [113.55554483194832]
文脈線形帯域設定における保守的学習問題について検討し、新しいアルゴリズムである保守的制約付きLinUCB(CLUCB2)を導入する。
我々は、既存の結果と一致したCLUCB2に対する後悔の限界を導き、多くの合成および実世界の問題において、最先端の保守的バンディットアルゴリズムよりも優れていることを実証的に示す。
論文 参考訳(メタデータ) (2020-02-08T19:35:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。