論文の概要: Stochastic Direct Search Method for Blind Resource Allocation
- arxiv url: http://arxiv.org/abs/2210.05222v2
- Date: Tue, 01 Oct 2024 08:15:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-02 16:31:42.379925
- Title: Stochastic Direct Search Method for Blind Resource Allocation
- Title（参考訳）: ブラインド資源配置の確率的直接探索法
- Authors: Juliette Achddou, Olivier Cappe, Aurélien Garivier,
- Abstract要約: 線形制約付きおよび微分自由最適化のための直接探索法(パターン探索とも呼ばれる)について検討する。
直接探索法は決定論的かつ制約のない場合において有限の後悔を達成できることを示す。
そこで本研究では,T2/3$のオーダを後悔させるようなダイレクトサーチの簡単な拡張を提案する。
- 参考スコア（独自算出の注目度）: 6.574808513848414
- License:
- 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, with the objective of maximizing the number of conversions. We study direct search (also known as pattern search) methods for linearly constrained and derivative-free optimization in the presence of noise, which apply in particular to sequential budget allocation. These algorithms, which do not rely on hierarchical partitioning of the resource space, are easy to implement; they respect the operational constraints of resource allocation by avoiding evaluation outside of the feasible domain; and they are also compatible with warm start by being (approximate) descent algorithms. However, they have not yet been analyzed from the perspective of cumulative regret. We show that direct search methods achieves finite regret in the deterministic and unconstrained case. In the presence of evaluation noise and linear constraints, we propose a simple extension of direct search that achieves a regret upper-bound of the order of $T^{2/3}$. We also propose an accelerated version of the algorithm, relying on repeated sequential testing, that significantly improves the practical behavior of the approach.
- Abstract（参考訳）: プログラム的広告最適化によって動機づけられた予算を一連の資源に順次割り当てる作業について検討する。
ステップ毎に、実現可能なアロケーションが選択され、対応するランダムリターンのみが観察される。
目標は、期待されるリターンの累積総和を最大化することである。
これはマーケティングキャンペーンの部門をまたいだ予算配分の現実的なモデルであり、変換の数を最大化することを目的としている。
本稿では,特に逐次予算配分に適用される雑音の存在下での線形制約および微分自由度最適化のための直接探索法(パターン探索とも呼ばれる)について検討する。
これらのアルゴリズムは、リソース空間の階層的分割に依存しないため、実装が容易であり、実行可能なドメインの外での評価を回避し、リソース割り当ての運用上の制約を尊重する。
しかし、累積的後悔の観点からはまだ分析されていない。
直接探索法は決定論的かつ制約のない場合において有限の後悔を達成できることを示す。
評価ノイズと線形制約の存在下では、T^{2/3}$の残差上限を達成できるような、直接探索の単純な拡張を提案する。
また,反復的な逐次テストに頼って,アルゴリズムの高速化版を提案し,アプローチの実践的振る舞いを大幅に改善する。
関連論文リスト
- Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time
Guarantees [56.848265937921354]
逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。
IRLの多くのアルゴリズムは本質的にネスト構造を持つ。
我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-04T17:13:45Z) - Structural Estimation of Markov Decision Processes in High-Dimensional
State Space with Finite-Time Guarantees [39.287388288477096]
本研究では,実施行動と訪問状態の観測可能な履歴に基づいて,人間エージェントによる動的決定の構造モデルの推定作業を検討する。
この問題には固有のネスト構造があり、内部問題では与えられた報酬関数に対する最適ポリシーが特定され、外部問題では適合度の測定が最大化される。
本研究では,高次元状態空間を扱うための有限時間保証付き単一ループ推定アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-10-04T00:11:38Z) - Budgeted Classification with Rejection: An Evolutionary Method with
Multiple Objectives [0.0]
予算付きシーケンシャル分類器(BSC)プロセスは、部分的特徴取得と評価ステップのシーケンスを通じて入力を行う。
これにより、不要な特徴取得を防止するための入力の効率的な評価が可能になる。
本稿では,信頼度に基づく拒否オプション付き逐次分類器を構築するための問題固有遺伝的アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-01T22:05:16Z) - Online Allocation with Two-sided Resource Constraints [44.5635910908944]
我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。
提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-28T02:21:06Z) - 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) - Variance Penalized On-Policy and Off-Policy Actor-Critic [60.06593931848165]
本稿では,平均値と変動値の両方を含むパフォーマンス基準を最適化する,オン・ポリティィおよびオフ・ポリティィ・アクター・クリティカルなアルゴリズムを提案する。
提案手法は, アクタ批判的かつ事前の分散-ペナライゼーションベースラインに匹敵するだけでなく, リターンのばらつきが低いトラジェクトリも生成する。
論文 参考訳（メタデータ） (2021-02-03T10:06:16Z) - Online Stochastic Optimization with Wasserstein Based Non-stationarity [12.91020811577007]
有限期間の地平線上の複数の予算制約を持つ一般的なオンライン最適化問題を検討する。
意思決定者の目標は、予算制約の対象となる累積報酬を最大化することである。
この定式化は、オンラインリニアプログラミングやネットワーク収益管理を含む幅広いアプリケーションを取り込む。
論文 参考訳（メタデータ） (2020-12-13T04:47:37Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Stochastic Adaptive Line Search for Differentially Private Optimization [6.281099620056346]
プライベート勾配に基づく最適化アルゴリズムの性能は、選択ステップサイズ(または学習率)に大きく依存する。
ノイズ勾配の信頼性に応じて、プライバシー勾配を調整する古典的非自明な行探索アルゴリズムを提案する。
適応的に選択されたステップサイズにより、提案アルゴリズムは、プライバシ予算を効率的に利用し、既存のプライベートグラデーションと競合する性能を示すことができる。
論文 参考訳（メタデータ） (2020-08-18T15:18:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。