論文の概要: 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とも呼ばれる)を推定する。
関連論文リスト
- 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$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
論文 参考訳（メタデータ） (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) - Risk-averse Contextual Multi-armed Bandit Problem with Linear Payoffs [7.125769932993104]
リスク・逆条件下での線形ペイオフに対するコンテキスト多重武装バンディット問題について考察する。
各ラウンドにおいて、各アームのコンテキストが明らかにされ、意思決定者は1つのアームを選択して、対応する報酬を受け取ります。
解離モデルに対してトンプソンサンプリングアルゴリズムを適用し,提案アルゴリズムの変種に対する包括的後悔解析を行う。
論文 参考訳（メタデータ） (2022-06-24T18:48:35Z) - 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) - Recurrent Submodular Welfare and Matroid Blocking Bandits [22.65352007353614]
最近の研究は、マルチアームバンディット問題(MAB)の研究に焦点をあてている。
我々は、任意のマトロイドに対して$ (1 - frac1e)$-approximation を得ることのできる新しいアルゴリズムのアイデアを開発した。
鍵となる要素は、相関的な(インターリーブされた)スケジューリング技術である。
論文 参考訳（メタデータ） (2021-01-30T21:51:47Z) - 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) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳（メタデータ） (2020-03-05T21:29:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。