論文の概要: Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits

• arxiv url: http://arxiv.org/abs/2309.00814v1
• Date: Sat, 2 Sep 2023 03:49:05 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-07 01:08:36.595493
• Title: Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits
• Title（参考訳）: シミュレーターをバイパスする : 準最適逆線形コンテキストバンディット
• Authors: Haolin Liu, Chen-Yu Wei, Julian Zimmert
• Abstract要約: 本稿では、損失ベクトルを全対角に選択し、ラウンドごとのアクションセットを固定分布から引き出す対角線形境界帯域問題について考察する。 この問題の既存の方法は、自由な文脈を生成するためにシミュレータへのアクセスを必要とするか、準最適後悔を達成するか、あるいは計算的に非効率である。 シミュレーションを使わずに$widetildeO(sqrtT)$を後悔して、各ラウンドで設定したアクションが小さい場合に計算効率を維持することで、これらの結果を大幅に改善する。
• 参考スコア（独自算出の注目度）: 30.337826346496385
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the adversarial linear contextual bandit problem, where the loss vectors are selected fully adversarially and the per-round action set (i.e. the context) is drawn from a fixed distribution. Existing methods for this problem either require access to a simulator to generate free i.i.d. contexts, achieve a sub-optimal regret no better than $\widetilde{O}(T^{\frac{5}{6}})$, or are computationally inefficient. We greatly improve these results by achieving a regret of $\widetilde{O}(\sqrt{T})$ without a simulator, while maintaining computational efficiency when the action set in each round is small. In the special case of sleeping bandits with adversarial loss and stochastic arm availability, our result answers affirmatively the open question by Saha et al. [2020] on whether there exists a polynomial-time algorithm with $poly(d)\sqrt{T}$ regret. Our approach naturally handles the case where the loss is linear up to an additive misspecification error, and our regret shows near-optimal dependence on the magnitude of the error.
• Abstract（参考訳）: 損失ベクトルが完全に逆向きに選択され、ラウンドごとのアクションセット(つまりコンテキスト)が固定分布から引き出される、逆線形文脈バンディット問題を考える。 この問題の既存の方法は、自由な文脈を生成するためにシミュレータへのアクセスを必要とするか、$\widetilde{O}(T^{\frac{5}{6}})$以上の最適でない後悔を達成するか、計算的に非効率である。 我々は,各ラウンドのアクションセットが小さい場合に計算効率を保ちながら,シミュレータを使わずに$\widetilde{O}(\sqrt{T})$を後悔することで,これらの結果を大幅に改善する。 対人的損失と確率的腕の可用性を伴う睡眠用バンディットの特別ケースでは,sahaらによるオープン質問に対して肯定的な回答が得られた。 [2020]$poly(d)\sqrt{T}$ regretの多項式時間アルゴリズムが存在するかどうかについて。 提案手法は, 損失が加法的不特定誤差まで線形である場合に自然に対処し, 後悔は誤差の大きさにほぼ最適に依存することを示す。

関連論文リスト

• Best-of-Both-Worlds Linear Contextual Bandits [45.378265414553226]
  本研究は, 対向汚職下での多武装盗賊問題の事例である$K$腕線形文脈盗賊の問題を考察する。 我々は,理論的保証のもと,双方の敵環境に有効な戦略を開発する。 両体制の理論的保証から,我々の戦略をBest-of-Both-Worlds (BoBW) RealFTRLと呼んでいる。
  論文  参考訳（メタデータ） (2023-12-27T09:32:18Z)
• 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)
• Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
  政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。 我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。 我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
  論文  参考訳（メタデータ） (2022-04-24T03:10:27Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Adversarial Combinatorial Bandits with General Non-linear Reward Functions [29.775097827244853]
  既知の非線形報酬関数を用いて対向性バンディットを研究し、対向性線形バンディットに関する既存の研究を延長する。 我々は、$N$の腕と$K$の腕のサブセットが$T$の期間のそれぞれで選択されている場合、ミニマックスの最適な後悔は$widetildeTheta_d(Nd T)$報酬関数が$dK$の$d$度であり、$ta_K(sqrtK T)$報酬関数が低度ではない場合です。
  論文  参考訳（メタデータ） (2021-01-05T00:56:27Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。 いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。 文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
  論文  参考訳（メタデータ） (2020-07-07T09:00:57Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits [13.32560004325655]
  古典的な$K$武器の線形文脈包帯問題の逆変法を考える。 $d$-dimensionalコンテキストがランダムに生成されるという仮定の下で、古典的なExp3アルゴリズムに基づいて効率的なアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-02-01T22:49:46Z)

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

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