論文の概要: Online Learning with Cumulative Oversampling: Application to Budgeted Influence Maximization

• arxiv url: http://arxiv.org/abs/2004.11963v3
• Date: Wed, 16 Sep 2020 01:51:09 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-10 03:17:32.697155
• Title: Online Learning with Cumulative Oversampling: Application to Budgeted Influence Maximization
• Title（参考訳）: 累積オーバーサンプリングによるオンライン学習:予算効果最大化への応用
• Authors: Shatian Wang, Shuoguang Yang, Zhen Xu, Van-Anh Truong
• Abstract要約: オンライン学習のための累積オーバー(CO)手法を提案する。 私たちのキーとなるアイデアは、各ラウンドで一度更新された信念空間からパラメータ推定をサンプリングすることです。 IMの半帯域に対して,我々のCOベースのアルゴリズムは,理論上はUPBベースのアルゴリズムに匹敵する規模の後悔を達成できることを示す。
• 参考スコア（独自算出の注目度）: 7.893654261799925
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a cumulative oversampling (CO) method for online learning. Our key idea is to sample parameter estimations from the updated belief space once in each round (similar to Thompson Sampling), and utilize the cumulative samples up to the current round to construct optimistic parameter estimations that asymptotically concentrate around the true parameters as tighter upper confidence bounds compared to the ones constructed with standard UCB methods. We apply CO to a novel budgeted variant of the Influence Maximization (IM) semi-bandits with linear generalization of edge weights, whose offline problem is NP-hard. Combining CO with the oracle we design for the offline problem, our online learning algorithm simultaneously tackles budget allocation, parameter learning, and reward maximization. We show that for IM semi-bandits, our CO-based algorithm achieves a scaled regret comparable to that of the UCB-based algorithms in theory, and performs on par with Thompson Sampling in numerical experiments.
• Abstract（参考訳）: オンライン学習のための累積オーバーサンプリング(CO)手法を提案する。 我々のキーとなる考え方は、各ラウンドで一度更新された信念空間からパラメータ推定をサンプリングし(トンプソンサンプリングと同様)、現在のラウンドまで累積サンプルを用いて、標準 UCB 法で構築されたものと比較して、真のパラメータの周りに漸近的に集中する楽観的なパラメータ推定を構築することである。 我々は, エッジウェイトを線形に一般化した影響最大化(IM)半帯域の新たな予算付き変種にCOを適用し, オフライン問題はNPハードである。 オフライン問題のために設計したオラクルとCOを組み合わせることで、オンライン学習アルゴリズムは予算配分、パラメータ学習、報酬の最大化に同時に取り組みます。 IMの半帯域に対して,我々のCOベースのアルゴリズムは理論上のUTBベースのアルゴリズムに匹敵する規模の後悔を達成し,数値実験でトンプソンサンプリングと同等に動作することを示す。

関連論文リスト

• Efficient Learning of POMDPs with Known Observation Model in Average-Reward Setting [56.92178753201331]
  我々は,POMDPパラメータを信念に基づくポリシを用いて収集したサンプルから学習することのできる観測・認識スペクトル(OAS)推定手法を提案する。 提案するOAS-UCRLアルゴリズムに対して,OASプロシージャの整合性を示し,$mathcalO(sqrtT log(T)$の残差保証を証明した。
  論文  参考訳（メタデータ） (2024-10-02T08:46:34Z)
• Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning [50.92957910121088]
  本研究は,情報指向サンプリング(IDS)の原理に基づくマルチエージェント強化学習(MARL)のための新しいアルゴリズムの設計と解析を行う。 エピソディックな2プレーヤゼロサムMGに対して、ナッシュ平衡を学習するための3つのサンプル効率アルゴリズムを提案する。 我々は、Reg-MAIDSをマルチプレイヤー汎用MGに拡張し、ナッシュ平衡または粗相関平衡をサンプル効率良く学習できることを証明する。
  論文  参考訳（メタデータ） (2024-04-30T06:48:56Z)
• Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration [87.53543137162488]
  我々はtextttMEX というオンライン強化学習(オンラインRL)フレームワークを提案する。 textttMEXは、自動的に探索エクスプロイトのバランスをとりながら、見積もりと計画コンポーネントを統合する。 様々な MuJoCo 環境では,ベースラインを安定的なマージンで上回り,十分な報酬を得られる。
  論文  参考訳（メタデータ） (2023-05-29T17:25:26Z)
• Multivariate Probabilistic CRPS Learning with an Application to Day-Ahead Electricity Prices [0.0]
  本稿では,多変量確率予測を結合(あるいは集約)する新しい手法を提案する。 オンライン学習を可能にするスムーズな手続きを通じて、量子と限界の間の依存関係を考察する。 提案アルゴリズムの高速なC++実装は、CRAN上のオープンソースのR-Package profocで提供される。
  論文  参考訳（メタデータ） (2023-03-17T14:47:55Z)
• Sparse high-dimensional linear regression with a partitioned empirical Bayes ECM algorithm [62.997667081978825]
  疎高次元線形回帰に対する計算効率が高く強力なベイズ的手法を提案する。 パラメータに関する最小の事前仮定は、プラグイン経験的ベイズ推定(英語版)を用いて用いられる。 提案手法はRパッケージプローブに実装されている。
  論文  参考訳（メタデータ） (2022-09-16T19:15:50Z)
• A Stochastic Bundle Method for Interpolating Networks [18.313879914379008]
  本稿では,実験的な損失をゼロにすることができるディープニューラルネットワークのトレーニング手法を提案する。 各イテレーションにおいて,本手法は目的学習近似のバンドルとして知られる最大線形近似を構成する。
  論文  参考訳（メタデータ） (2022-01-29T23:02:30Z)
• Adaptive Client Sampling in Federated Learning via Online Learning with Bandit Feedback [36.05851452151107]
  統合学習(FL)システムは、トレーニングの各ラウンドに関与するクライアントのサブセットをサンプリングする必要があります。 その重要性にもかかわらず、クライアントを効果的にサンプリングする方法には制限がある。 提案手法は,最適化アルゴリズムの収束速度をいかに向上させるかを示す。
  論文  参考訳（メタデータ） (2021-12-28T23:50:52Z)
• Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
  ランダムサンプリングではなく,ZO最適化における摂動を生成するためのサンプリングポリシを学習する,新たな強化学習ベースのZOアルゴリズムを提案する。 その結果,ZO-RLアルゴリズムはサンプリングポリシを学習することでZO勾配の分散を効果的に低減し,既存のZOアルゴリズムよりも高速に収束できることが示唆された。
  論文  参考訳（メタデータ） (2021-04-09T14:50:59Z)
• Adaptive Importance Sampling for Finite-Sum Optimization and Sampling with Decreasing Step-Sizes [4.355567556995855]
  ステップサイズを小さくした有限サム最適化とサンプリングのための適応的重要度サンプリングのための簡易かつ効率的なアルゴリズムであるavareを提案する。 標準的な技術的条件下では、$mathcalO(T2/3)$と$mathcalO(T5/6)$の動的後悔をそれぞれ、$mathcalO(T5/6)$のステップサイズで実行するときに達成している。
  論文  参考訳（メタデータ） (2021-03-23T00:28:15Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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