論文の概要: Randomized Policy Optimization for Optimal Stopping
- arxiv url: http://arxiv.org/abs/2203.13446v1
- Date: Fri, 25 Mar 2022 04:33:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-28 22:17:31.289052
- Title: Randomized Policy Optimization for Optimal Stopping
- Title（参考訳）: 最適停止のためのランダム化政策最適化
- Authors: Xinyi Guan, Velibor V. Mi\v{s}i\'c
- Abstract要約: 本稿では,ランダム化線形ポリシーに基づく最適停止手法を提案する。
提案手法は最先端手法を著しく上回り得ることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Optimal stopping is the problem of determining when to stop a stochastic
system in order to maximize reward, which is of practical importance in domains
such as finance, operations management and healthcare. Existing methods for
high-dimensional optimal stopping that are popular in practice produce
deterministic linear policies -- policies that deterministically stop based on
the sign of a weighted sum of basis functions -- but are not guaranteed to find
the optimal policy within this policy class given a fixed basis function
architecture. In this paper, we propose a new methodology for optimal stopping
based on randomized linear policies, which choose to stop with a probability
that is determined by a weighted sum of basis functions. We motivate these
policies by establishing that under mild conditions, given a fixed basis
function architecture, optimizing over randomized linear policies is equivalent
to optimizing over deterministic linear policies. We formulate the problem of
learning randomized linear policies from data as a smooth non-convex sample
average approximation (SAA) problem. We theoretically prove the almost sure
convergence of our randomized policy SAA problem and establish bounds on the
out-of-sample performance of randomized policies obtained from our SAA problem
based on Rademacher complexity. We also show that the SAA problem is in general
NP-Hard, and consequently develop a practical heuristic for solving our
randomized policy problem. Through numerical experiments on a benchmark family
of option pricing problem instances, we show that our approach can
substantially outperform state-of-the-art methods.
- Abstract（参考訳）: 最適停止とは、報酬を最大化するために確率的システムをいつ停止するかを決定する問題であり、これは金融、経営管理、医療といった分野において事実上重要である。
既存の高次元の最適停止法は、決定論的線形ポリシー -- 基底関数の重み付き和の符号に基づいて決定論的に停止するポリシー -- を生み出しているが、固定基底関数アーキテクチャによって与えられたこのポリシークラス内で最適なポリシーを見つけることは保証されていない。
本稿では,基本関数の重み付け和によって決定される確率で停止する確率を選択する,ランダム化線形ポリシーに基づく最適停止法を提案する。
穏やかな条件下では、固定基底関数アーキテクチャが与えられた場合、ランダム化された線形ポリシーを最適化することは決定論的線形ポリシーを最適化するのと同じである。
本研究では,データからランダムな線形ポリシーを学習する問題を,滑らかな非凸サンプル平均近似(saa)問題として定式化する。
理論的には、ランダム化政策SAA問題のほぼ確実な収束を証明し、Radecher複雑性に基づくランダム化政策のアウト・オブ・サンプル性能の限界を確立する。
また, SAA 問題は一般のNP-Hard の問題であり, ランダム化政策問題を解くための実践的ヒューリスティックを発達させることを示す。
オプション価格問題インスタンスのベンチマークファミリに関する数値実験により,提案手法が最先端の手法を大幅に上回ることを示す。
関連論文リスト
- Strongly-polynomial time and validation analysis of policy gradient methods [3.722665817361884]
本稿では,有限状態および行動マルコフ決定過程(MDP)と強化学習(RL)のための,優位ギャップ関数と呼ばれる新しい終了基準を提案する。
この利点ギャップ関数をステップサイズルールの設計に組み込むことで、最適ポリシーの定常状態分布に依存しない新しい線形収束率を導出する。
政策勾配法に対してそのような強い収束特性が確立されたのはこれが初めてである。
論文 参考訳（メタデータ） (2024-09-28T18:56:48Z) - Importance-Weighted Offline Learning Done Right [16.4989952150404]
文脈的帯域幅問題におけるオフラインポリシー最適化の問題について検討する。
目標は、準最適行動ポリシーによって収集された決定データのデータセットに基づいて、ほぼ最適ポリシーを学ぶことである。
我々は、citet2015の「単純探索」推定に基づく単純な代替手法が、過去の全ての結果よりもほぼ全ての可能な条件で優れた性能保証を与えることを示した。
論文 参考訳（メタデータ） (2023-09-27T16:42:10Z) - Last-Iterate Convergent Policy Gradient Primal-Dual Methods for
Constrained MDPs [107.28031292946774]
無限水平割引マルコフ決定過程(拘束型MDP)の最適ポリシの計算問題について検討する。
我々は, 最適制約付きポリシーに反復的に対応し, 非漸近収束性を持つ2つの単一スケールポリシーに基づく原始双対アルゴリズムを開発した。
我々の知る限り、この研究は制約付きMDPにおける単一時間スケールアルゴリズムの非漸近的な最後の収束結果となる。
論文 参考訳（メタデータ） (2023-06-20T17:27:31Z) - High-probability sample complexities for policy evaluation with linear function approximation [88.87036653258977]
本研究では,2つの広く利用されている政策評価アルゴリズムに対して,最適線形係数の予め定義された推定誤差を保証するために必要なサンプル複素量について検討する。
高確率収束保証に縛られた最初のサンプル複雑性を確立し、許容レベルへの最適依存を実現する。
論文 参考訳（メタデータ） (2023-05-30T12:58:39Z) - Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time
Guarantees [56.848265937921354]
逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。
IRLの多くのアルゴリズムは本質的にネスト構造を持つ。
我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-04T17:13:45Z) - Sample Complexity of Policy-Based Methods under Off-Policy Sampling and
Linear Function Approximation [8.465228064780748]
政策評価には、オフ政治サンプリングと線形関数近似を用いる。
自然政策勾配(NPG)を含む様々な政策更新規則が政策更新のために検討されている。
我々は、最適なポリシーを見つけるために、合計$mathcalO(epsilon-2)$サンプルの複雑さを初めて確立する。
論文 参考訳（メタデータ） (2022-08-05T15:59:05Z) - Off-Policy Evaluation with Policy-Dependent Optimization Response [90.28758112893054]
我々は,テキスト政治に依存した線形最適化応答を用いた非政治評価のための新しいフレームワークを開発した。
摂動法による政策依存推定のための非バイアス推定器を構築する。
因果介入を最適化するための一般的なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-02-25T20:25:37Z) - Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
最適化手法の優位性は、正確な勾配が用いられるかどうかに大きく依存することを示す。
次に,政策最適化におけるコミット率の概念を紹介する。
第三に、外部のオラクル情報がない場合には、収束を加速するために幾何を利用することと、最適性をほぼ確実に達成することとの間に本質的にトレードオフがあることが示される。
論文 参考訳（メタデータ） (2021-10-29T06:35:44Z) - A Reinforcement Learning Approach to the Stochastic Cutting Stock
Problem [0.0]
本稿では,削減された無限水平決定プロセスとして,カットストック問題の定式化を提案する。
最適解は、各状態と決定を関連付け、期待される総コストを最小化するポリシーに対応する。
論文 参考訳（メタデータ） (2021-09-20T14:47:54Z) - Doubly Robust Off-Policy Value and Gradient Estimation for Deterministic
Policies [80.42316902296832]
本研究では,行動継続時の非政治データから決定論的政策の政策値と勾配を推定する。
この設定では、密度比が存在しないため、標準重要度サンプリングとポリシー値と勾配の2倍の頑健な推定が失敗する。
異なるカーネル化アプローチに基づく2つの新しい頑健な推定器を提案する。
論文 参考訳（メタデータ） (2020-06-06T15:52:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。