論文の概要: Multi-armed Bandit Requiring Monotone Arm Sequences

• arxiv url: http://arxiv.org/abs/2106.03790v2
• Date: Tue, 8 Jun 2021 19:52:14 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-10 13:58:41.299362
• Title: Multi-armed Bandit Requiring Monotone Arm Sequences
• Title（参考訳）: モノトンアームシーケンスを必要とするマルチアームバンド
• Authors: Ningyuan Chen
• Abstract要約: 腕列が単調である必要がある場合の連続武器バンドイット問題について考察する。 未知の目的関数がリプシッツ連続であるとき、後悔は提案アルゴリズムの下で$tilde O(T3/4)$であることを示す。 これは、連続武装バンディット文学における最適レート$tilde O(T2/3)$から逸脱し、単調性要求によってもたらされる学習効率のコストを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In many online learning or multi-armed bandit problems, the taken actions or pulled arms are ordinal and required to be monotone over time. Examples include dynamic pricing, in which the firms use markup pricing policies to please early adopters and deter strategic waiting, and clinical trials, in which the dose allocation usually follows the dose escalation principle to prevent dose limiting toxicities. We consider the continuum-armed bandit problem when the arm sequence is required to be monotone. We show that when the unknown objective function is Lipschitz continuous, the regret is $O(T)$. When in addition the objective function is unimodal or quasiconcave, the regret is $\tilde O(T^{3/4})$ under the proposed algorithm, which is also shown to be the optimal rate. This deviates from the optimal rate $\tilde O(T^{2/3})$ in the continuous-armed bandit literature and demonstrates the cost to the learning efficiency brought by the monotonicity requirement.
• Abstract（参考訳）: 多くのオンライン学習やマルチアームの盗賊問題では、取られた行動や引き出された腕は規則的であり、時間とともに単調でなければならない。 例えば、企業が早期採用者や戦略的な待機を緩和するためにマークアップ価格ポリシーを使用する動的価格設定や、線量配分は通常、線量制限毒性を防止するために線量エスカレーション原則に従う臨床試験などがある。 腕列が単調である必要がある場合の連続腕包帯問題を考える。 未知の目的関数がリプシッツ連続であるとき、後悔は$O(T)$であることを示す。 さらに、目的関数がユニモーダルあるいは準凹である場合、その後悔は、提案されたアルゴリズムの下で$\tilde o(t^{3/4})$であり、これは最適速度でもある。 これは、連続武装バンディット文学における最適レート$\tilde O(T^{2/3})$から逸脱し、単調性要求によってもたらされる学習効率のコストを示す。

関連論文リスト

• Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
  Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。 本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
  論文  参考訳（メタデータ） (2024-09-09T18:23:07Z)
• Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback [11.262167746929332]
  Restless Multi-armed bandits (RMAB)は、シーケンシャルな意思決定問題のモデル化において中心的な役割を果たす。 本稿では,未知の遷移関数と対向報酬を持つ表在的RMABにおける学習課題について考察する。 我々は2つの重要な貢献者による新しい強化学習アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-05-02T02:20:19Z)
• Weighted Tallying Bandits: Overcoming Intractability via Repeated Exposure Optimality [46.445321251991096]
  推薦システムやクラウドソーシングアプリケーションでは、人間の好みや能力はアルゴリズムの最近の行動の関数であることが多い。 我々は、この設定を一般化するWeighted Tallying Bandit (WTB)を導入し、アクションの損失が、前回の$m$のタイムステップで腕が演奏された回数のエンフ和関数であることを要求して、この設定を一般化する。 我々は、$K$アクションと水平線$T$の問題に対して、逐次除去アルゴリズムの簡単な変更は、$O left( sqrtKT + m+)を持つことを示した。
  論文  参考訳（メタデータ） (2023-05-04T15:59:43Z)
• Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
  我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。 学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。 コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
  論文  参考訳（メタデータ） (2021-06-18T15:01:01Z)
• Asymptotically Optimal Bandits under Weighted Information [10.939683083130616]
  エージェントが各ラウンドで複数のアームを演奏できるマルチアームバンディット装置における後悔の問題について検討する。 本稿では,Thompson-Sampling ベースの戦略を提案する。この戦略は,各腕が最高の腕であるという後続の信念として,パワープロファイルを設計する。
  論文  参考訳（メタデータ） (2021-05-28T21:28:44Z)
• Recurrent Submodular Welfare and Matroid Blocking Bandits [22.65352007353614]
  最近の研究は、マルチアームバンディット問題(MAB)の研究に焦点をあてている。 我々は、任意のマトロイドに対して$ (1 - frac1e)$-approximation を得ることのできる新しいアルゴリズムのアイデアを開発した。 鍵となる要素は、相関的な(インターリーブされた)スケジューリング技術である。
  論文  参考訳（メタデータ） (2021-01-30T21:51:47Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。 いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。 文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
  論文  参考訳（メタデータ） (2020-07-07T09:00:57Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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