論文の概要: Online Algorithm for Unsupervised Sequential Selection with Contextual
Information
- arxiv url: http://arxiv.org/abs/2010.12353v1
- Date: Fri, 23 Oct 2020 12:32:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-03 21:49:49.881057
- Title: Online Algorithm for Unsupervised Sequential Selection with Contextual
Information
- Title(参考訳): 文脈情報を用いた教師なしシーケンス選択のためのオンラインアルゴリズム
- Authors: Arun Verma, Manjesh K. Hanawal, Csaba Szepesv\'ari, Venkatesh
Saligrama
- Abstract要約: 文脈教師なしシーケンス選択(USS)について検討する。
USSは、観測されたフィードバックから腕の喪失を推測できない文脈的包帯問題の新しい変種である。
本稿では,文脈的 USS 問題に対するアルゴリズムを提案し,それがサブ線形後悔であることを示す。
- 参考スコア(独自算出の注目度): 38.47252956961143
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we study Contextual Unsupervised Sequential Selection (USS), a
new variant of the stochastic contextual bandits problem where the loss of an
arm cannot be inferred from the observed feedback. In our setup, arms are
associated with fixed costs and are ordered, forming a cascade. In each round,
a context is presented, and the learner selects the arms sequentially till some
depth. The total cost incurred by stopping at an arm is the sum of fixed costs
of arms selected and the stochastic loss associated with the arm. The learner's
goal is to learn a decision rule that maps contexts to arms with the goal of
minimizing the total expected loss. The problem is challenging as we are faced
with an unsupervised setting as the total loss cannot be estimated. Clearly,
learning is feasible only if the optimal arm can be inferred (explicitly or
implicitly) from the problem structure. We observe that learning is still
possible when the problem instance satisfies the so-called 'Contextual Weak
Dominance' (CWD) property. Under CWD, we propose an algorithm for the
contextual USS problem and demonstrate that it has sub-linear regret.
Experiments on synthetic and real datasets validate our algorithm.
- Abstract(参考訳): 本稿では,観測されたフィードバックからアームの損失を推測できない確率的文脈的バンディット問題の新たな変種である文脈的非教師なし逐次選択(uss)について検討する。
私たちの設定では、アームは固定コストと関連付けられて、カスケードを形成します。
各ラウンドでコンテキストが提示され、学習者が一定の深さまで順次アームを選択する。
腕の停止による総コストは、選択された腕の固定コストと腕に関連する確率損失の合計である。
学習者の目標は、コンテキストをアームにマップする決定ルールを学習し、期待される損失を最小化することである。
総損失を見積もることができないため、教師なしの設定に直面しているため、問題は難しい。
明らかに、学習は最適な腕が問題構造から(明示的または暗黙的に)推論できる場合にのみ実現可能である。
問題インスタンスがいわゆる"コンテキスト弱支配(Contextual Weak Dominance)"(CWD)特性を満たす場合,学習は依然として可能である。
CWDでは,文脈的 USS 問題に対するアルゴリズムを提案し,サブ線形後悔が存在することを示す。
合成および実データセットの実験は、我々のアルゴリズムを検証する。
関連論文リスト
- Optimal cross-learning for contextual bandits with unknown context
distributions [28.087360479901978]
本稿では,バルセイロ等のクロスラーニング環境において,文脈的包括的アルゴリズムを設計する際の問題点について考察する。
コンテクスト数によらずに$widetildeO(sqrtTK)$というほぼ厳密な(対数的要因まで)後悔境界を持つ効率的なアルゴリズムを提供する。
アルゴリズムのコアとなるのは,複数のエポックにまたがるアルゴリズムの実行をコーディネートする新しい手法である。
論文 参考訳(メタデータ) (2024-01-03T18:02:13Z) - 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) - Stochastic Contextual Dueling Bandits under Linear Stochastic
Transitivity Models [25.336599480692122]
我々は,コンテキスト情報を用いた決闘バンディット問題における後悔の最小化タスクについて検討する。
本稿では,フィードバックプロセスの模倣に基づく計算効率のよいアルゴリズムである$texttCoLSTIM$を提案する。
本実験は,CoLSTモデルの特殊事例に対する最先端アルゴリズムよりも優れていることを示す。
論文 参考訳(メタデータ) (2022-02-09T17:44:19Z) - Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。
学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。
コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
論文 参考訳(メタデータ) (2021-06-18T15:01:01Z) - 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) - Restless-UCB, an Efficient and Low-complexity Algorithm for Online
Restless Bandits [61.490254407420906]
我々は、各腕の状態がマルコフ連鎖に従って進化するオンラインレス・バンディット問題について研究する。
本研究では,探索研究の枠組みに従う学習方針であるReestless-UCBを提案する。
論文 参考訳(メタデータ) (2020-11-05T05:16:04Z) - Thompson Sampling for Unsupervised Sequential Selection [3.5436187733613087]
教師なしシークエンシャルセレクション(USS)問題に対するトンプソンサンプリングに基づくアルゴリズムについて検討する。
USS問題(英語: USS problem)は、観測されたフィードバックから腕の喪失を推測できないマルチアームバンディット問題の変種である。
我々は,Thompson Sampling をベースとした USS 問題に対するアルゴリズムが,ほぼ最適な後悔を達成し,既存のアルゴリズムよりも優れた数値性能を有することを示す。
論文 参考訳(メタデータ) (2020-09-16T08:48:17Z) - Contextual Blocking Bandits [35.235375147227124]
我々は,多腕バンディット問題の新たな変種について検討し,各ステップごとに,腕の平均報酬を決定する独立したサンプルコンテキストをプレイヤーが観察する。
アームを再生することで(すべてのコンテキストにわたって)将来の時間ステップの固定および既知の回数をブロックする。
我々は、$mathcalO(log T)$-regret w.r.t.$alpha$regret戦略を$Tタイムステップで保証し、$Omega(log(T)$low boundと一致する UCB ベースのフル情報アルゴリズムの変種を提案する。
論文 参考訳(メタデータ) (2020-03-06T20:34:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。