論文の概要: Adversarial Rewards in Universal Learning for Contextual Bandits

• arxiv url: http://arxiv.org/abs/2302.07186v2
• Date: Mon, 12 Jun 2023 16:52:27 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-14 01:10:29.036133
• Title: Adversarial Rewards in Universal Learning for Contextual Bandits
• Title（参考訳）: 文脈帯域のユニバーサル学習における逆戻り
• Authors: Moise Blanchard, Steve Hanneke and Patrick Jaillet
• Abstract要約: 本研究では,学習者の報酬が行動や既知の文脈に依存する状況において,学習の限界について検討する。 対人報酬を伴う文脈的包帯に対する楽観的普遍学習は一般に不可能であることを示す。
• 参考スコア（独自算出の注目度）: 32.14208422566497
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the fundamental limits of learning in contextual bandits, where a learner's rewards depend on their actions and a known context, which extends the canonical multi-armed bandit to the case where side-information is available. We are interested in universally consistent algorithms, which achieve sublinear regret compared to any measurable fixed policy, without any function class restriction. For stationary contextual bandits, when the underlying reward mechanism is time-invariant, Blanchard et. al (2022) characterized learnable context processes for which universal consistency is achievable; and further gave algorithms ensuring universal consistency whenever this is achievable, a property known as optimistic universal consistency. It is well understood, however, that reward mechanisms can evolve over time, possibly adversarially, and depending on the learner's actions. We show that optimistic universal learning for contextual bandits with adversarial rewards is impossible in general, contrary to all previously studied settings in online learning -- including standard supervised learning. We also give necessary and sufficient conditions for universal learning under various adversarial reward models, and an exact characterization for online rewards. In particular, the set of learnable processes for these reward models is still extremely general -- larger than i.i.d., stationary or ergodic -- but in general strictly smaller than that for supervised learning or stationary contextual bandits, shedding light on new adversarial phenomena.
• Abstract（参考訳）: 本研究では,学習者の報酬が行動や既知の文脈に依存する文脈バンディットにおける学習の基本的な限界について検討する。 我々は、関数クラス制限なしに、任意の測定可能な固定ポリシーと比較してsublinear regretを実現する、普遍的に一貫性のあるアルゴリズムに興味を持っている。 定常的文脈的バンディットの場合、基礎となる報酬機構が時間不変である場合、buckhardなど。 al (2022) は普遍的一貫性が達成可能である学習可能な文脈過程を特徴付け、さらに楽観的普遍的一貫性と呼ばれる性質が達成可能であれば普遍的一貫性を保証するアルゴリズムを与えた。 しかし、報酬機構は時間とともに進化し、おそらく逆転し、学習者の行動に依存することがよく理解されている。 We show that optimistic universal learning for contextual bandits with adversarial rewards is impossible in general, contrary to all previously studied settings in online learning -- including standard supervised learning. We also give necessary and sufficient conditions for universal learning under various adversarial reward models, and an exact characterization for online rewards. In particular, the set of learnable processes for these reward models is still extremely general -- larger than i.i.d., stationary or ergodic -- but in general strictly smaller than that for supervised learning or stationary contextual bandits, shedding light on new adversarial phenomena.

関連論文リスト

• Contextual Bandits and Optimistically Universal Learning [32.14208422566497]
  私たちは一貫性に重点を置いています -- 最適な政策に比べて後悔を消します。 非i.d.文脈の大規模クラスでは、時間不変の報酬機構によらず一貫性が達成できることが示される。
  論文  参考訳（メタデータ） (2022-12-31T16:15:28Z)
• On the Complexity of Representation Learning in Contextual Linear Bandits [110.84649234726442]
  表現学習は線形帯域よりも根本的に複雑であることを示す。 特に、与えられた表現の集合で学ぶことは、その集合の中で最悪の実現可能な表現で学ぶことよりも決して単純ではない。
  論文  参考訳（メタデータ） (2022-12-19T13:08:58Z)
• Modeling Multiple Views via Implicitly Preserving Global Consistency and Local Complementarity [61.05259660910437]
  複数の視点から表現を学習するために,グローバルな一貫性と相補性ネットワーク(CoCoNet)を提案する。 グローバルな段階では、重要な知識はビュー間で暗黙的に共有され、そのような知識を捕捉するためのエンコーダの強化は、学習された表現の識別性を向上させることができる。 最後に、局所的な段階において、横断的な識別的知識を結合する相補的要素を提案し、また、エンコーダが視点的識別性だけでなく、横断的な相補的情報も学習するように誘導する。
  論文  参考訳（メタデータ） (2022-09-16T09:24:00Z)
• Universal Regression with Adversarial Responses [26.308541799686505]
  非I.d.インスタンスシーケンスの大規模クラスの下で、逆応答を伴う回帰のためのアルゴリズムを提供する。 我々は,学習者の強い一貫性を求める普遍的な一貫性を,値応答の制限なしに検討する。
  論文  参考訳（メタデータ） (2022-03-09T22:10:30Z)
• Universal Online Learning: an Optimistically Universal Learning Rule [0.0]
  本研究では,非i.d.プロセスを用いたユニバーサルオンライン学習の課題について検討する。 k-nearest neighbor algorithm (kNN) は楽観的に普遍的ではなく, 1NN の新たな変種を示す。
  論文  参考訳（メタデータ） (2022-01-16T02:13:47Z)
• Constructing a Good Behavior Basis for Transfer using Generalized Policy Updates [63.58053355357644]
  そこで我々は,優れた政策集合を学習する問題を考察し,組み合わせることで,目に見えない多種多様な強化学習タスクを解くことができることを示した。 理論的には、独立したポリシーのセットと呼ぶ、特定の多様なポリシーのセットにアクセスできることによって、ハイレベルなパフォーマンスを即時に達成できることが示される。
  論文  参考訳（メタデータ） (2021-12-30T12:20:46Z)
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective [104.67295710363679]
  古典的なマルチアームバンディット問題において、インスタンス依存アルゴリズムは、ベストとセカンドベストのアーム間のギャップで「容易」な問題のパフォーマンスを向上させる。 我々は、インスタンス依存の後悔境界を得るのに十分かつ必要である複雑性尺度のファミリーを導入する。 次に、可能な限りギャップに適応する新しいオラクル効率アルゴリズムを導入し、最悪の場合にはミニマックスレートを得る。
  論文  参考訳（メタデータ） (2020-10-07T01:33:06Z)
• Contextual Bandit with Missing Rewards [27.066965426355257]
  文脈に基づく決定に関連付けられた報酬が必ずしも観測されないような、文脈的包帯問題の新しい変種を考察する。 この新しい問題は、臨床試験や広告レコメンデーションアプリケーションを含む特定のオンライン設定によって動機付けられている。 本稿では,クラスタリングのような教師なし学習機構と,標準的な文脈的帯域幅アプローチを組み合わせることを提案する。
  論文  参考訳（メタデータ） (2020-07-13T13:29:51Z)
• Reward-Conditioned Policies [100.64167842905069]
  模倣学習には、ほぼ最適の専門家データが必要である。 実演なしで指導的学習を通じて効果的な政策を学べるか? 政策探索の原則的手法として,このようなアプローチを導出する方法を示す。
  論文  参考訳（メタデータ） (2019-12-31T18:07:43Z)

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

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