論文の概要: Thompson Sampling for Unsupervised Sequential Selection

• arxiv url: http://arxiv.org/abs/2009.07554v1
• Date: Wed, 16 Sep 2020 08:48:17 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-17 23:10:00.252379
• Title: Thompson Sampling for Unsupervised Sequential Selection
• Title（参考訳）: 教師なしシーケンス選択のためのトンプソンサンプリング
• Authors: Arun Verma, Manjesh K. Hanawal, Nandyala Hemachandra
• Abstract要約: 教師なしシークエンシャルセレクション(USS)問題に対するトンプソンサンプリングに基づくアルゴリズムについて検討する。 USS問題(英語: USS problem)は、観測されたフィードバックから腕の喪失を推測できないマルチアームバンディット問題の変種である。 我々は,Thompson Sampling をベースとした USS 問題に対するアルゴリズムが,ほぼ最適な後悔を達成し,既存のアルゴリズムよりも優れた数値性能を有することを示す。
• 参考スコア（独自算出の注目度）: 3.5436187733613087
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Thompson Sampling has generated significant interest due to its better empirical performance than upper confidence bound based algorithms. In this paper, we study Thompson Sampling based algorithm for Unsupervised Sequential Selection (USS) problem. The USS problem is a variant of the stochastic multi-armed bandits problem, where the loss of an arm can not be inferred from the observed feedback. In the USS setup, arms are associated with fixed costs and are ordered, forming a cascade. In each round, the learner selects an arm and observes the feedback from arms up to the selected arm. The learner's goal is to find the arm that minimizes the expected total loss. The total loss is the sum of the cost incurred for selecting the arm and the stochastic loss associated with the selected arm. The problem is challenging because, without knowing the mean loss, one cannot compute the total loss for the selected arm. Clearly, learning is feasible only if the optimal arm can be inferred from the problem structure. As shown in the prior work, learning is possible when the problem instance satisfies the so-called `Weak Dominance' (WD) property. Under WD, we show that our Thompson Sampling based algorithm for the USS problem achieves near optimal regret and has better numerical performance than existing algorithms.
• Abstract（参考訳）: トンプソンサンプリングは、高信頼のバウンドベースアルゴリズムよりも優れた経験的性能のために大きな関心を集めている。 本稿では,教師なしシーケンス選択(USS)問題に対するトンプソンサンプリングに基づくアルゴリズムについて検討する。 USS問題は、観測されたフィードバックから腕の喪失を推測できない確率的マルチアームバンディット問題の変種である。 USSセットアップでは、アームは固定コストと関連付けられ、カスケードを形成する。 各ラウンドで、学習者は腕を選択し、選択した腕までの腕からのフィードバックを観察する。 学習者の目標は、期待される総損失を最小限に抑えるアームを見つけることである。 総損失は、アームの選択に要するコストと、選択されたアームに関連する確率的損失の合計である。 平均損失を知らずに、選択したアームの総損失を計算することができないため、問題は難しい。 明らかに、学習は最適な腕が問題構造から推測できる場合にのみ実現可能である。 先行研究で示されているように、問題インスタンスがいわゆる「弱支配」(wd)特性を満たすと学習が可能になる。 WDの下では,我々のトンプソンサンプリングに基づくUSS問題に対するアルゴリズムは,ほぼ最適に後悔し,既存のアルゴリズムよりも優れた数値性能を有することを示す。

関連論文リスト

• Contextual Bandits with Arm Request Costs and Delays [19.263086804406786]
  本稿では,時間的遅延と関連するコストを伴って,新たなアームセットを要求できるコンテキスト的バンディット問題の拡張を提案する。 この設定では、学習者は、各選択が1つの時間単位を取るように、決定セットから複数のアームを選択することができる。 我々は、武器を効果的に選択し、新しい武器を要求する適切な時間を決定するアルゴリズムを設計し、彼らの後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2024-10-17T00:44:50Z)
• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
  論文  参考訳（メタデータ） (2024-09-08T12:19:12Z)
• Neural Dueling Bandits [58.90189511247936]
  ニューラルネットワークを用いて、予め選択した腕の好みフィードバックを用いて報酬関数を推定する。 次に、理論結果を二項フィードバックによる文脈的帯域幅問題に拡張し、それはそれ自体は自明な寄与ではない。
  論文  参考訳（メタデータ） (2024-07-24T09:23:22Z)
• Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget [6.22018632187078]
  固定予算の制約付きベスト・ミックスアーム識別(CBMAI)問題を導入する。 目標は、与えられた学習予算$N$で、期待されるコストの制約によって期待される報酬を最大化する最高の混合アームを見つけることである。 我々は、(最良の混合アームの支持の)誤識別に関する理論上の上限を提供し、予算$N$で指数関数的に崩壊することを示す。
  論文  参考訳（メタデータ） (2024-05-23T22:35:11Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。 まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。 我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
  論文  参考訳（メタデータ） (2021-02-15T19:10:52Z)
• Online Model Selection: a Rested Bandit Formulation [49.69377391589057]
  静止したバンディット設定における最善のアーム識別問題を紹介し,解析する。 我々は、この問題の後悔の新しい概念を定義し、ゲームの終わりに最小の期待損失を持つ腕を常に再生するポリシーと比較します。 最近のバンディット文献における既知のモデル選択の試みとは異なり、アルゴリズムは問題の特定の構造を利用して、予想される損失関数の未知のパラメータを学習する。
  論文  参考訳（メタデータ） (2020-12-07T08:23:08Z)
• Online Algorithm for Unsupervised Sequential Selection with Contextual Information [38.47252956961143]
  文脈教師なしシーケンス選択(USS)について検討する。 USSは、観測されたフィードバックから腕の喪失を推測できない文脈的包帯問題の新しい変種である。 本稿では,文脈的 USS 問題に対するアルゴリズムを提案し,それがサブ線形後悔であることを示す。
  論文  参考訳（メタデータ） (2020-10-23T12:32:21Z)
• The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity [83.81297078039836]
  インセンティブ付き探索(Incentivized Exploring)は、武器の選択を自給自足エージェントによって制御するマルチアーム・バンディットのバージョンである。 我々は、インセンティブの価格に焦点を合わせ、インセンティブの適合性のために、広く解釈された、パフォーマンスの喪失が引き起こされる。
  論文  参考訳（メタデータ） (2020-02-03T04:58:51Z)

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

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