論文の概要: Learning and Optimization with Seasonal Patterns

• arxiv url: http://arxiv.org/abs/2005.08088v4
• Date: Sun, 22 Aug 2021 14:28:47 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-02 12:58:08.120937
• Title: Learning and Optimization with Seasonal Patterns
• Title（参考訳）: 季節パターンによる学習と最適化
• Authors: Ningyuan Chen, Chun Wang, Longlin Wang
• Abstract要約: 平均報酬が周期的に変化するK$アームを持つ非定常MABモデルを考える。 本稿では,信頼関係分析と学習手順を組み合わせて未知の期間を学習する2段階ポリシーを提案する。 我々の学習ポリシーは、後悔の上限である $tildeO(sqrtTsum_k=1K T_k)$ ここで、$T_k$はarm $k$の期間であることを示す。
• 参考スコア（独自算出の注目度）: 3.7578900993400626
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A standard assumption adopted in the multi-armed bandit (MAB) framework is that the mean rewards are constant over time. This assumption can be restrictive in the business world as decision-makers often face an evolving environment where the mean rewards are time-varying. In this paper, we consider a non-stationary MAB model with $K$ arms whose mean rewards vary over time in a periodic manner. The unknown periods can be different across arms and scale with the length of the horizon $T$ polynomially. We propose a two-stage policy that combines the Fourier analysis with a confidence-bound-based learning procedure to learn the periods and minimize the regret. In stage one, the policy correctly estimates the periods of all arms with high probability. In stage two, the policy explores the periodic mean rewards of arms using the periods estimated in stage one and exploits the optimal arm in the long run. We show that our learning policy incurs a regret upper bound $\tilde{O}(\sqrt{T\sum_{k=1}^K T_k})$ where $T_k$ is the period of arm $k$. Moreover, we establish a general lower bound $\Omega(\sqrt{T\max_{k}\{ T_k\}})$ for any policy. Therefore, our policy is near-optimal up to a factor of $\sqrt{K}$.
• Abstract（参考訳）: mab(multi-armed bandit)フレームワークで採用されている標準的な仮定は、平均報酬は時間とともに一定であるということである。 この仮定は、意思決定者がしばしば平均的な報酬が経時的に変化する環境に直面するため、ビジネスの世界では制限される可能性がある。 本稿では、平均報酬が時間とともに周期的に変化するK$アームを持つ非定常MABモデルについて考察する。 未知の周期は腕とスケールで異なり、水平線の長さは多項式的に$t$である。 本稿では,Fourier分析と信頼度に基づく学習手法を組み合わせた2段階のポリシーを提案し,その期間を学習し,後悔を最小限に抑える。 ステージ1では、ポリシーはすべての腕の期間を高い確率で正確に推定する。 第2段階において、この政策は、第1段階で推定される期間を用いて、腕の周期平均報酬を探索し、長期的に最適な腕を利用する。 我々の学習ポリシーは、後悔の上限である$\tilde{O}(\sqrt{T\sum_{k=1}^K T_k})$に対して、$T_k$はarm $k$の期間であることを示す。 さらに、任意のポリシーに対して、一般的な下界$\Omega(\sqrt{T\max_{k}\{T_k\}})$を確立する。 したがって、我々のポリシーは、$\sqrt{K}$にほぼ最適である。

関連論文リスト

• Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
  Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。 本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
  論文  参考訳（メタデータ） (2024-09-09T18:23:07Z)
• Multi-Armed Bandits with Interference [39.578572123342944]
  スイッチバックポリシは,最高の固定アームポリシに対して,最適に期待された後悔のO(sqrt T)$を達成できることが示される。 提案するクラスタランダム化ポリシは,期待値に最適である。
  論文  参考訳（メタデータ） (2024-02-02T19:02:47Z)
• Allocating Divisible Resources on Arms with Unknown and Random Rewards [25.93048671326331]
  我々は、各期間に複数の武器で再生可能資源の1単位を割り当てる意思決定者について検討する。 アームは未知でランダムな報酬であり、その手段は割り当てられたリソースに比例し、分散は割り当てられたリソースのオーダー$b$に比例する。
  論文  参考訳（メタデータ） (2023-06-28T21:59:11Z)
• Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption [12.471848976031904]
  基本的な目標は、腕の数($N$)が大きくなるにつれて、最適性のギャップを小さくするポリシーを効率的に計算することである。 既存の最適性に関する結果は、すべて一様大域的誘引特性(UGAP)に依存している。 我々は,任意の単一武器のポリシーを元の$N$武器の問題に対するポリシーに変換する,汎用的なシミュレーションベースのフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-05-31T21:26:43Z)
• Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
  クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。 我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
  論文  参考訳（メタデータ） (2023-04-25T09:31:20Z)
• Tractable Optimality in Episodic Latent MABs [75.17357040707347]
  我々は、エージェントが時間ステップ$H$のエピソードのために環境と対話する、M$遅延コンテキストを持つマルチアームバンディット問題を考える。 エピソードの長さによっては、学習者は遅れた文脈を正確に見積もることができないかもしれない。 我々は、$O(textttpoly(A) + textttpoly(M,H)min(M,H))$インタラクションを用いて、ほぼ最適なポリシーを確実に学習する手順を設計する。
  論文  参考訳（メタデータ） (2022-10-05T22:53:46Z)
• Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
  我々は,各ラウンドの開始時に,学習者が各アームの真の報酬について,ノイズのない独立した評価を受けるマルチアームバンディット・セッティングを考える。 評価の方法によって異なるアルゴリズムアプローチと理論的保証を導出する。
  論文  参考訳（メタデータ） (2021-12-13T09:48:54Z)
• Continuous Time Bandits With Sampling Costs [17.412117389855222]
  連続時間マルチアームバンディット問題 (CTMAB) を考えると, 学習者は任意の間隔で何回でもアームをサンプリングし, サンプルからランダムな報酬を得ることができる。 サンプリング周波数の関数として、大きな報酬を得ることとサンプリングコストをもたらすことにはトレードオフがある。 目的は後悔を最小限に抑える学習アルゴリズムを設計することであり、これはオラクルのポリシーと学習アルゴリズムの報酬の差として定義される。
  論文  参考訳（メタデータ） (2021-07-12T10:00:35Z)
• Dynamic Planning and Learning under Recovering Rewards [18.829837839926956]
  我々は「純粋周期ポリシー」のクラスの性能保証を提案し、構築し、証明する。 私たちのフレームワークとポリシー設計は、他のオフライン計画およびオンライン学習アプリケーションに適応する可能性がある。
  論文  参考訳（メタデータ） (2021-06-28T15:40:07Z)
• Combinatorial Bandits without Total Order for Arms [52.93972547896022]
  セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。 我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
  論文  参考訳（メタデータ） (2021-03-03T23:08:59Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。 まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。 我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
  論文  参考訳（メタデータ） (2021-02-15T19:10:52Z)

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

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