Exploratory Optimal Stopping: A Singular Control Formulation

• URL: http://arxiv.org/abs/2408.09335v2
• Date: Wed, 2 Oct 2024 13:13:06 GMT
• Title: Exploratory Optimal Stopping: A Singular Control Formulation
• Authors: Jodi Dianetti, Giorgio Ferrari, Renyuan Xu,
• Abstract summary: We explore continuous-time and state-space optimal stopping problems from a reinforcement learning perspective. We introduce a regularized version of the problem by penalizing it with the cumulative residual entropy of the randomized stopping time. For the specific case of a real option problem, we derive a semiexplicit solution to the regularized problem.
• Score: 2.7309692684728613
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper explores continuous-time and state-space optimal stopping problems from a reinforcement learning perspective. We begin by formulating the stopping problem using randomized stopping times, where the decision maker's control is represented by the probability of stopping within a given time--specifically, a bounded, non-decreasing, c\`adl\`ag control process. To encourage exploration and facilitate learning, we introduce a regularized version of the problem by penalizing it with the cumulative residual entropy of the randomized stopping time. The regularized problem takes the form of an (n+1)-dimensional degenerate singular stochastic control with finite-fuel. We address this through the dynamic programming principle, which enables us to identify the unique optimal exploratory strategy. For the specific case of a real option problem, we derive a semi-explicit solution to the regularized problem, allowing us to assess the impact of entropy regularization and analyze the vanishing entropy limit. Finally, we propose a reinforcement learning algorithm based on policy iteration. We show both policy improvement and policy convergence results for our proposed algorithm.

Related papers

• Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning [62.81324245896717]
  We introduce an exploration-agnostic algorithm, called C-PG, which exhibits global last-ite convergence guarantees under (weak) gradient domination assumptions. We numerically validate our algorithms on constrained control problems, and compare them with state-of-the-art baselines.
  arXiv  Detail & Related papers  (2024-07-15T14:54:57Z)
• Randomized algorithms and PAC bounds for inverse reinforcement learning in continuous spaces [47.907236421762626]
  This work studies discrete-time discounted Markov decision processes with continuous state and action spaces. We first consider the case in which we have access to the entire expert policy and characterize the set of solutions to the inverse problem.
  arXiv  Detail & Related papers  (2024-05-24T12:53:07Z)
• Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
  We propose a model-based primal-dual algorithm to learn in an unknown CMDP. We prove that our algorithm achieves sublinear regret without error cancellations.
  arXiv  Detail & Related papers  (2024-02-24T09:47:46Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  Inverse reinforcement learning (IRL) aims to recover the reward function and the associated optimal policy. Many algorithms for IRL have an inherently nested structure. We develop a novel single-loop algorithm for IRL that does not compromise reward estimation accuracy.
  arXiv  Detail & Related papers  (2022-10-04T17:13:45Z)
• Optimal scheduling of entropy regulariser for continuous-time linear-quadratic reinforcement learning [9.779769486156631]
  Herein agent interacts with the environment by generating noisy controls distributed according to the optimal relaxed policy. This exploration-exploitation trade-off is determined by the strength of entropy regularisation. We prove that the regret, for both learning algorithms, is of the order $mathcalO(sqrtN) $ (up to a logarithmic factor) over $N$ episodes, matching the best known result from the literature.
  arXiv  Detail & Related papers  (2022-08-08T23:36:40Z)
• Linear convergence of a policy gradient method for finite horizon continuous time stochastic control problems [3.7971225066055765]
  This paper proposes a provably convergent gradient method for general continuous space-time control problems. We show that the algorithm converges linearly to the point of control, and is stable with respect to policy by steps.
  arXiv  Detail & Related papers  (2022-03-22T14:17:53Z)
• Instance-Dependent Confidence and Early Stopping for Reinforcement Learning [99.57168572237421]
  Various algorithms for reinforcement learning (RL) exhibit dramatic variation in their convergence rates as a function of problem structure. This research provides guarantees that explain textitex post the performance differences observed. A natural next step is to convert these theoretical guarantees into guidelines that are useful in practice.
  arXiv  Detail & Related papers  (2022-01-21T04:25:35Z)
• Conservative Distributional Reinforcement Learning with Safety Constraints [22.49025480735792]
  Safety exploration can be regarded as a constrained Markov decision problem where the expected long-term cost is constrained. Previous off-policy algorithms convert the constrained optimization problem into the corresponding unconstrained dual problem by introducing the Lagrangian relaxation technique. We present a novel off-policy reinforcement learning algorithm called Conservative Distributional Maximum a Posteriori Policy Optimization.
  arXiv  Detail & Related papers  (2022-01-18T19:45:43Z)
• Optimization Issues in KL-Constrained Approximate Policy Iteration [48.24321346619156]
  Many reinforcement learning algorithms can be seen as versions of approximate policy iteration (API) While standard API often performs poorly, it has been shown that learning can be stabilized by regularizing each policy update by the KL-divergence to the previous policy. Popular practical algorithms such as TRPO, MPO, and VMPO replace regularization by a constraint on KL-divergence of consecutive policies.
  arXiv  Detail & Related papers  (2021-02-11T19:35:33Z)
• Continuous-Time Multi-Armed Bandits with Controlled Restarts [32.63624728528415]
  We investigate the bandit problem with controlled restarts for time-constrained decision processes. In particular, we consider a bandit setting where each decision takes a random completion time, and yields a random and correlated reward at the end. We develop efficient online learning algorithms with $O(log(tau))$ and $O(sqrttaulog(tau))$ regret in a finite and continuous action space of restart strategies.
  arXiv  Detail & Related papers  (2020-06-30T19:50:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.