論文の概要: 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はこの設定を簡単な修正によって適切に調整できることを示す。

関連論文リスト

• Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints [8.784438985280094]
  線形制約が未知の多腕バンディットにおける純粋探索として問題を研究する。 まず、制約下での純粋な探索のために、サンプルの複雑さを低く抑えたラグランジアン緩和を提案する。 第二に、ラグランジアンの下界と凸の性質を利用して、トラック・アンド・ストップとガミファイド・エクスプローラー(LATSとLAGEX)の2つの計算効率の良い拡張を提案する。
  論文  参考訳（メタデータ） (2024-10-24T15:26:14Z)
• Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints [29.514323697659613]
  我々は,学習者が任意の長期制約を満たすことなく報酬を最大化することを目的とした,knapsacks問題によるバンディットの一般化に対処する。 私たちのゴールは、双方の制約の下で機能するベスト・オブ・ザ・ワールドのアルゴリズムを設計することです。
  論文  参考訳（メタデータ） (2024-05-25T08:09:36Z)
• Batched Nonparametric Contextual Bandits [21.031965676746776]
  バッチ制約下での非パラメトリック文脈帯域について検討する。 最適な後悔を実現する新しいバッチ学習アルゴリズムを提案する。 我々の理論的結果は、非パラメトリックな文脈的帯域幅では、ほぼ一定数のポリシー更新が最適な後悔をもたらすことを示唆している。
  論文  参考訳（メタデータ） (2024-02-27T18:06:20Z)
• Interactively Learning Preference Constraints in Linear Bandits [100.78514640066565]
  我々は、既知の報酬と未知の制約で逐次意思決定を研究する。 応用として,運転シミュレーションにおいて,人間の嗜好を表現するための学習制約を検討する。
  論文  参考訳（メタデータ） (2022-06-10T17:52:58Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。