論文の概要: Regret Analysis of the Stochastic Direct Search Method for Blind
Resource Allocation
- arxiv url: http://arxiv.org/abs/2210.05222v1
- Date: Tue, 11 Oct 2022 07:40:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-12 17:33:56.178644
- Title: Regret Analysis of the Stochastic Direct Search Method for Blind
Resource Allocation
- Title(参考訳): ブラインド資源配分のための確率的直接探索法の後悔解析
- Authors: Juliette Achddou (PSL, DI-ENS), Olivier Cappe (CNRS, DI-ENS, PSL),
Aur\'elien Garivier (UMPA-ENSL, CNRS)
- Abstract要約: 雑音の存在下での線形制約および微分自由度最適化のための直接探索法(パターン探索)について検討した。
一般の場合、T2/3の次数に対する後悔の上限を与える。
我々の数学的分析は、決定論的で制約のないケースにおいて、副産物として、時間非依存の後悔境界を定めている。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by programmatic advertising optimization, we consider the task of
sequentially allocating budget across a set of resources. At every time step, a
feasible allocation is chosen and only a corresponding random return is
observed. The goal is to maximize the cumulative expected sum of returns. This
is a realistic model for budget allocation across subdivisions of marketing
campaigns, when the objective is to maximize the number of conversions. We
study direct search (aka pattern search) methods for linearly constrained and
derivative-free optimization in the presence of noise. Those algorithms are
easy to implement and particularly suited to constrained optimization. They
have not yet been analyzed from the perspective of cumulative regret. We
provide a regret upper-bound of the order of T 2/3 in the general case. Our
mathematical analysis also establishes, as a by-product, time-independent
regret bounds in the deterministic, unconstrained case. We also propose an
improved version of the method relying on sequential tests to accelerate the
identification of descent directions.
- Abstract(参考訳): プログラム的な広告最適化に動機づけられ,予算をリソースの集合に順次割り当てる作業を考える。
ステップ毎に、実現可能なアロケーションが選択され、対応するランダムリターンのみが観察される。
目標は、累積的なリターンの合計を最大化することである。
これは、コンバージョン数を最大化することを目的としたマーケティングキャンペーンのサブディビジョンにまたがる予算配分の現実的なモデルである。
雑音の存在下での線形制約および微分自由度最適化のための直接探索法(パターン探索)について検討した。
これらのアルゴリズムは実装が容易であり、特に制約付き最適化に適している。
累積的な後悔の観点からはまだ分析されていない。
一般の場合、T2/3の次数に対する後悔の上限を与える。
我々の数学的分析は、決定論的で制約のないケースにおいて、副産物として、時間非依存の後悔境界を確立する。
また,降下方向の同定を高速化するために,逐次試験に依存する手法の改良版を提案する。
関連論文リスト
- Random Exploration in Bayesian Optimization: Order-Optimal Regret and
Computational Efficiency [18.17090625880964]
本研究では,分布から引き出されたランダムサンプルを用いて領域を探索する手法について検討する。
このランダム探索手法が最適誤差率を達成することを示す。
論文 参考訳(メタデータ) (2023-10-23T20:30:44Z) - Constrained Online Two-stage Stochastic Optimization: Near Optimal
Algorithms via Adversarial Learning [1.994307489466967]
有限地平線上の長期制約付きオンライン2段階最適化をT$周期で検討する。
対戦型学習アルゴリズムからオンライン二段階問題のオンラインアルゴリズムを開発する。
論文 参考訳(メタデータ) (2023-02-02T10:33:09Z) - Generalizing Bayesian Optimization with Decision-theoretic Entropies [102.82152945324381]
統計的決定論の研究からシャノンエントロピーの一般化を考える。
まず,このエントロピーの特殊なケースがBO手順でよく用いられる獲得関数に繋がることを示す。
次に、損失に対する選択肢の選択が、どのようにして柔軟な獲得関数の族をもたらすかを示す。
論文 参考訳(メタデータ) (2022-10-04T04:43:58Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳(メタデータ) (2021-10-09T21:13:48Z) - Local policy search with Bayesian optimization [73.0364959221845]
強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。
局所探索のための政策勾配は、しばしばランダムな摂動から得られる。
目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
論文 参考訳(メタデータ) (2021-06-22T16:07:02Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳(メタデータ) (2021-06-05T09:16:28Z) - Nonstationary Reinforcement Learning with Linear Function Approximation [24.910327525332463]
ドリフト環境下での線形関数近似によるマルコフ決定過程(MDP)における強化学習について考察する。
我々はまず、$textttLSVI-UCB-Restart$アルゴリズムを開発し、変動予算が分かっている場合にその動的後悔境界を確立する。
次にパラメータフリーアルゴリズムである$textttAda-LSVI-UCB-Restart$を提案する。
論文 参考訳(メタデータ) (2020-10-08T20:07:44Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Alternating Direction Method of Multipliers for Quantization [15.62692130672419]
量子化のための乗算器の交互方向法(texttADMM-Q$)アルゴリズムの性能について検討する。
不正確な更新ルールを処理できる$texttADMM-Q$のいくつかのバリエーションを開発しています。
提案手法の有効性を実証的に評価した。
論文 参考訳(メタデータ) (2020-09-08T01:58:02Z) - Stochastic Optimization Forests [60.523606291705214]
標準的なランダムな森林アルゴリズムのように予測精度を向上させるために分割するのではなく、分割を選択した木を栽培し、下流の意思決定品質を直接最適化することで、森林決定政策の訓練方法を示す。
概略分割基準は、各候補分割に対して正確に最適化された森林アルゴリズムに近い性能を保ちながら、100倍のランニング時間を短縮できることを示す。
論文 参考訳(メタデータ) (2020-08-17T16:56:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。