論文の概要: 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問題に対するアルゴリズムは,ほぼ最適に後悔し,既存のアルゴリズムよりも優れた数値性能を有することを示す。
関連論文リスト
- Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [56.457634640638254]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳(メタデータ) (2023-10-02T08:15:52Z) - Finding Optimal Arms in Non-stochastic Combinatorial Bandits with
Semi-bandit Feedback and Finite Budget [6.759124697337311]
有限サンプリング予算制約の下では,半帯域フィードバックによる帯域幅問題を考える。
アクションは、一組のアームを選択し、選択されたセット内の各アームに対するフィードバックが受信される。
本稿では,アーム除去戦略の全スペクトルをカバーするのに適した汎用アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-02-09T14:36:05Z) - 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) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳(メタデータ) (2020-08-10T08:30:52Z) - The Price of Incentivizing Exploration: A Characterization via Thompson
Sampling and Sample Complexity [83.81297078039836]
インセンティブ付き探索(Incentivized Exploring)は、武器の選択を自給自足エージェントによって制御するマルチアーム・バンディットのバージョンである。
我々は、インセンティブの価格に焦点を合わせ、インセンティブの適合性のために、広く解釈された、パフォーマンスの喪失が引き起こされる。
論文 参考訳(メタデータ) (2020-02-03T04:58:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。