論文の概要: Asymptotically Optimal Bandits under Weighted Information
- arxiv url: http://arxiv.org/abs/2105.14114v1
- Date: Fri, 28 May 2021 21:28:44 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-01 17:31:33.298082
- Title: Asymptotically Optimal Bandits under Weighted Information
- Title（参考訳）: 重み付き情報による漸近的最適帯域
- Authors: Matias I. M\"uller and Cristian R. Rojas
- Abstract要約: エージェントが各ラウンドで複数のアームを演奏できるマルチアームバンディット装置における後悔の問題について検討する。
本稿では,Thompson-Sampling ベースの戦略を提案する。この戦略は,各腕が最高の腕であるという後続の信念として,パワープロファイルを設計する。
- 参考スコア（独自算出の注目度）: 10.939683083130616
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We study the problem of regret minimization in a multi-armed bandit setup
where the agent is allowed to play multiple arms at each round by spreading the
resources usually allocated to only one arm. At each iteration the agent
selects a normalized power profile and receives a Gaussian vector as outcome,
where the unknown variance of each sample is inversely proportional to the
power allocated to that arm. The reward corresponds to a linear combination of
the power profile and the outcomes, resembling a linear bandit. By spreading
the power, the agent can choose to collect information much faster than in a
traditional multi-armed bandit at the price of reducing the accuracy of the
samples. This setup is fundamentally different from that of a linear bandit --
the regret is known to scale as $\Theta(\sqrt{T})$ for linear bandits, while in
this setup the agent receives a much more detailed feedback, for which we
derive a tight $\log(T)$ problem-dependent lower-bound. We propose a
Thompson-Sampling-based strategy, called Weighted Thompson Sampling (\WTS),
that designs the power profile as its posterior belief of each arm being the
best arm, and show that its upper bound matches the derived logarithmic lower
bound. Finally, we apply this strategy to a problem of control and system
identification, where the goal is to estimate the maximum gain (also called
$\mathcal{H}_\infty$-norm) of a linear dynamical system based on batches of
input-output samples.
- Abstract（参考訳）: 本研究では,通常1本の腕に割り当てられる資源を分散させることで,エージェントが各ラウンドで複数の腕を演奏できるマルチアームバンディット装置における後悔の最小化問題について検討する。
各イテレーションで、エージェントは正規化されたパワープロファイルを選択し、結果としてガウスベクトルを受け取り、そこでは各サンプルの未知の分散が、そのアームに割り当てられたパワーに逆比例する。
報酬は、電力プロファイルと結果の線形結合に対応しており、線形バンディットに似ている。
パワーを広げることで、エージェントは、サンプルの精度を下げる価格で、従来のマルチアームバンディットよりもはるかに早く情報を集めることができる。
この設定は、線形バンディットとは根本的に異なる - この後悔は、線形バンディットに対して$\Theta(\sqrt{T})$としてスケールすることが知られているが、この設定では、エージェントはより詳細なフィードバックを受け、そこでは、厳密な$\log(T)$問題依存ローバウンドを導出する。
Weighted Thompson Sampling (\WTS) と呼ばれるThompson-Sampling ベースの戦略を提案し、各アームが最適アームであることを示す後続の信念としてパワープロファイルを設計し、その上限が導出した対数下界と一致することを示す。
最後に、この戦略を制御とシステム同定の問題に適用し、入出力サンプルのバッチに基づいて線形力学系の最大ゲイン($\mathcal{h}_\infty$-normとも呼ばれる)を推定する。
関連論文リスト
- Continuous K-Max Bandits [54.21533414838677]
我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。
この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。
我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
論文 参考訳（メタデータ） (2025-02-19T06:37:37Z) - Fixed-Confidence Best Arm Identification with Decreasing Variance [12.018304940341793]
腕の報酬の変動を時間的に減少させるマルチアームバンディットにおけるベストアーム識別の問題に焦点をあてる。
学習者によるコストは、最適な腕を特定するのに必要な時間の重み付けされた和としてモデル化される。
論文 参考訳（メタデータ） (2025-02-11T02:47:20Z) - An Algorithm for Fixed Budget Best Arm Identification with Combinatorial Exploration [3.9901365062418312]
我々は、K$$armed banditフレームワークにおける最適な腕識別問題を考察する。
エージェントは1つのアームではなく、各タイムスロットでアームのサブセットをプレイすることができる。
我々は、$log K$グループを構築し、最適なアームの存在を検出するための確率比テストを実行するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-02-03T15:10:08Z) - Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。
本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
論文 参考訳（メタデータ） (2024-09-09T18:23:07Z) - A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Thompson Exploration with Best Challenger Rule in Best Arm
Identification [66.33448474838342]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳（メタデータ） (2023-10-01T01:37:02Z) - Beyond the Best: Estimating Distribution Functionals in Infinite-Armed
Bandits [40.71199236098642]
無限武装バンディット問題では、各アームの平均報酬は未知の分布からサンプリングされる。
我々は、最大以上の分布関数の一般的なクラスを検討し、オフラインとオンラインの両方で統一されたメタアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-11-01T18:20:10Z) - Finite-Time Regret of Thompson Sampling Algorithms for Exponential
Family Multi-Armed Bandits [88.21288104408556]
本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。
最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
論文 参考訳（メタデータ） (2022-06-07T18:08:21Z) - Scale Free Adversarial Multi Armed Bandits [13.757095663704858]
本稿では,MAB(Scale-Free Adversarial Multi Armed Bandit)問題について考察する。
我々はFTRLアルゴリズムを設計するが、これはMABに対する最初の無スケールな後悔の保証が伴う。
また,Bregman Divergencesの局所ノルム下界を求める新しい手法を開発した。
論文 参考訳（メタデータ） (2021-06-08T21:26:57Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。