論文の概要: Quantile Multi-Armed Bandits with 1-bit Feedback

• arxiv url: http://arxiv.org/abs/2502.06678v1
• Date: Mon, 10 Feb 2025 17:03:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-11 14:33:56.614733
• Title: Quantile Multi-Armed Bandits with 1-bit Feedback
• Title（参考訳）: 1ビットフィードバックをもつ量子多元帯域
• Authors: Ivan Lau, Jonathan Scarlett,
• Abstract要約: リスク感度と通信制約の要素を含むベストアーム識別のバリエーションについて検討する。 本研究では,雑音の多い二分探索をサブルーチンとして利用し,学習者が1ビットフィードバックによって定量報酬を推定できるアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 40.22079522118723
• License:
• Abstract: In this paper, we study a variant of best-arm identification involving elements of risk sensitivity and communication constraints. Specifically, the goal of the learner is to identify the arm with the highest quantile reward, while the communication from an agent (who observes rewards) and the learner (who chooses actions) is restricted to only one bit of feedback per arm pull. We propose an algorithm that utilizes noisy binary search as a subroutine, allowing the learner to estimate quantile rewards through 1-bit feedback. We derive an instance-dependent upper bound on the sample complexity of our algorithm and provide an algorithm-independent lower bound for specific instances, with the two matching to within logarithmic factors under mild conditions, or even to within constant factors in certain low error probability scaling regimes. The lower bound is applicable even in the absence of communication constraints, and thus we conclude that restricting to 1-bit feedback has a minimal impact on the scaling of the sample complexity.
• Abstract（参考訳）: 本稿では,リスク感度と通信制約の要素を含むベストアーム識別のバリエーションについて検討する。 具体的には、学習者の目標は、最も高い量的報酬で腕を識別することであり、一方、エージェント(報酬を観察する)と学習者(行動を選択する)とのコミュニケーションは、アームプル毎に1ビットのフィードバックに制限される。 本研究では,雑音の多い二分探索をサブルーチンとして利用し,学習者が1ビットフィードバックによって定量報酬を推定できるアルゴリズムを提案する。 我々は,アルゴリズムのサンプル複雑性に基づいて,インスタンス依存上界を導出し,アルゴリズム非依存下界を特定のインスタンスに対して提供し,その2つを軽度条件下での対数係数内,あるいは特定の低誤差確率スケーリング方式における定数要素内までマッチングする。 通信制約がない場合でも下界は適用可能であり、1ビットフィードバックの制限はサンプルの複雑さのスケーリングに与える影響を最小限に抑えると結論付ける。

関連論文リスト

• Best Arm Identification with Minimal Regret [55.831935724659175]
  最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。 エージェントの目標は、所定の信頼度で最高の腕を特定することである。 二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
  論文  参考訳（メタデータ） (2024-09-27T16:46:02Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Pure Exploration under Mediators' Feedback [63.56002444692792]
  マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。 本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。 本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
  論文  参考訳（メタデータ） (2023-08-29T18:18:21Z)
• Selective Sampling and Imitation Learning via Online Regression [17.73844193143454]
  雑音の多い専門家にフィードバックを求めることで,Imitation Learning (IL) の問題を考える。 我々は、選択的サンプリングを用いて、ノイズの多い専門家にフィードバックを積極的に問い合わせる、ILのための対話的アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2023-07-11T03:32:20Z)
• Interactively Learning Preference Constraints in Linear Bandits [100.78514640066565]
  我々は、既知の報酬と未知の制約で逐次意思決定を研究する。 応用として,運転シミュレーションにおいて,人間の嗜好を表現するための学習制約を検討する。
  論文  参考訳（メタデータ） (2022-06-10T17:52:58Z)
• Solving Multi-Arm Bandit Using a Few Bits of Communication [42.13277217013971]
  マルチアームバンディット問題(マルチアームバンディット問題、MAB)は、報酬を逐次観察することで、一連のアクションの中からベストを選択することを目的とした、アクティブな学習フレームワークである。 分散エージェントが収集した報酬の通信を最適化することで,コミュニケーション問題に対処する。 汎用的な報酬量子化アルゴリズムQuBanを構築し、任意の(非回帰的な)MABアルゴリズムの上に適用して、新しい通信効率の対物を形成する。
  論文  参考訳（メタデータ） (2021-11-11T06:23:16Z)
• Improved Algorithms for Agnostic Pool-based Active Classification [20.12178157010804]
  プールに依存しない環境でのバイナリ分類のためのアクティブラーニングを検討する。 我々のアルゴリズムは、画像分類データセットにおけるアートアクティブな学習アルゴリズムの状況よりも優れている。
  論文  参考訳（メタデータ） (2021-05-13T18:24:30Z)
• Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Scheme [16.1694012177079]
  我々は,多腕バンディットにおける最高の武器識別問題,潜在的に私的な報酬について検討する。 ゴールは、固定された所定のレベルで、最も高い定量値を持つ腕を特定することである。 このアルゴリズムは$delta$-PACであり,サンプルの複雑さを特徴付ける。
  論文  参考訳（メタデータ） (2020-06-11T20:23:43Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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