論文の概要: Non-stationary Contextual Bandits and Universal Learning
- arxiv url: http://arxiv.org/abs/2302.07186v1
- Date: Tue, 14 Feb 2023 16:54:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-15 14:50:00.655510
- Title: Non-stationary Contextual Bandits and Universal Learning
- 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.] 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
depending on the learner's actions. We show that optimistic universal learning
for non-stationary contextual bandits 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 non-stationarity models, including online and
adversarial reward mechanisms. In particular, the set of learnable processes
for non-stationary rewards 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
non-stationary phenomena.
- Abstract（参考訳）: 本研究では,学習者の報酬が行動や既知の文脈に依存する文脈バンディットにおける学習の基本的な限界について検討する。
我々は、関数クラス制限なしに、任意の測定可能な固定ポリシーと比較してsublinear regretを実現する、普遍的に一貫性のあるアルゴリズムに興味を持っている。
定常的な文脈的包帯に対して、基礎となる報酬機構が時間不変であるとき、[Blanchard et al.]は普遍的一貫性が達成可能な学習可能な文脈過程を特徴付ける。
しかし、報酬メカニズムは、おそらく学習者の行動によって、時間とともに進化する可能性があることはよく理解されている。
我々は,非定常的文脈的バンディットに対する楽観的な普遍的学習は一般に不可能であることを示す。
また,オンラインおよび広告報酬機構を含む様々な非定常モデルの下での普遍学習に必要十分条件を与える。
特に、非定常報酬の学習可能な過程の集合は、いまだに非常に一般的なものであり、すなわち、定常的あるいはエルゴード的なものであるが、一般には、教師付き学習や定常的文脈的包帯よりも厳密に小さく、新しい非定常現象に光を当てる。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。