論文の概要: 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 問題に対するアルゴリズムを提案し,サブ線形後悔が存在することを示す。 合成および実データセットの実験は、我々のアルゴリズムを検証する。

関連論文リスト

• 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)
• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす 本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。 本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
  論文  参考訳（メタデータ） (2024-04-16T17:59:55Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(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)
• Online Model Selection: a Rested Bandit Formulation [49.69377391589057]
  静止したバンディット設定における最善のアーム識別問題を紹介し,解析する。 我々は、この問題の後悔の新しい概念を定義し、ゲームの終わりに最小の期待損失を持つ腕を常に再生するポリシーと比較します。 最近のバンディット文献における既知のモデル選択の試みとは異なり、アルゴリズムは問題の特定の構造を利用して、予想される損失関数の未知のパラメータを学習する。
  論文  参考訳（メタデータ） (2020-12-07T08:23:08Z)
• 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)

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

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