Optimal stopping for partially observed piecewise-deterministic Markov processes

This paper deals with the optimal stopping problem under partial observation for piecewise-deterministic Markov processes. We first obtain a recursive formulation of the optimal filter process and derive the dynamic programming equation of the partially observed optimal stopping problem. Then, we propose a numerical method, based on the quantization of the discrete-time filter process and the inter-jump times, to approximate the value function and to compute an ?$?$-optimal stopping time. We prove the convergence of the algorithms and bound the rates of convergence.     

Optimal stopping of strong Markov processes

We characterize the value function and the optimal stopping time for a large class of optimal stopping problems where the underlying process to be stopped is a fairly general Markov process. The main result is inspired by recent findings for Lévy processes obtained essentially via the Wiener–Hopf factorization. The main ingredient in our approach is the representation of the β$\beta$-excessive functions as expected suprema. A variety of examples is given.     

Backward stochastic differential equations associated to jump Markov processes and applications

In this paper we study backward stochastic differential equations (BSDEs) driven by the compensated random measure associated to a given pure jump Markov process X$X$ on a general state space K$K$. We apply these results to prove well-posedness of a class of nonlinear parabolic differential equations on K$K$, that generalize the Kolmogorov equation of X$X$. Finally we formulate and solve optimal control problems for Markov jump processes, relating the value function and the optimal control law to an appropriate BSDE that also allows to construct probabilistically the unique solution to the Hamilton–Jacobi–Bellman equation and to identify it with the value function.     

Time discretization and quantization methods for optimal multiple switching problem

In this paper, we study probabilistic numerical methods based on optimal quantization algorithms for computing the solution to optimal multiple switching problems with regime-dependent state process. We first consider a discrete-time approximation of the optimal switching problem, and analyse its rate of convergence. Given a time step h$h$, the error is in general of order (hlog(1/h))^1/2${(hlog(1/h))}^{1/2}$, and of order h^1/2$h^{1/2}$ when the switching costs do not depend on the state process. We next propose quantization numerical schemes for the space discretization of the discrete-time Euler state process. A Markovian quantization approach relying on the optimal quantization of the normal distribution arising in the Euler scheme is analysed. In the particular case of uncontrolled state process, we describe an alternative marginal quantization method, which extends the recursive algorithm for optimal stopping problems as in Bally (2003) [1]. A priori L^p$L^p$-error estimates are stated in terms of quantization errors. Finally, some numerical tests are performed for an optimal switching problem with two regimes.     

Stochastic optimal multi-modes switching with a viscosity solution approach

We consider the problem of optimal multi-modes switching in finite horizon, when the state of the system, including the switching cost functions are arbitrary (_gij(t,x)≥0$g_{ij}(t,x)\ge 0$). We show existence of the optimal strategy, via a verification theorem. Finally, when the state of the system is a Markov process, we show that the vector of value functions of the optimal problem is the unique viscosity solution to the system of m$m$ variational partial differential inequalities with inter-connected obstacles.     

Explicit error bounds for lazy reversible Markov chain Monte Carlo

We prove explicit, i.e., non-asymptotic, error bounds for Markov Chain Monte Carlo methods, such as the Metropolis algorithm. The problem is to compute the expectation (or integral) of f$f$ with respect to a measure π$\pi$ which can be given by a density ?$?$ with respect to another measure. A straight simulation of the desired distribution by a random number generator is in general not possible. Thus it is reasonable to use Markov chain sampling with a burn-in. We study such an algorithm and extend the analysis of Lovasz and Simonovits [L. Lovász, M. Simonovits, Random walks in a convex body and an improved volume algorithm, Random Structures Algorithms 4 (4) (1993) 359–412] to obtain an explicit error bound.     

Quadratic reflected BSDEs with unbounded obstacles

In this paper, we analyze a real-valued reflected backward stochastic differential equation (RBSDE) with an unbounded obstacle and an unbounded terminal condition when its generator f$f$ has quadratic growth in the z$z$-variable. In particular, we obtain existence, uniqueness, and stability results, and consider the optimal stopping for quadratic g$g$-evaluations. As an application of our results we analyze the obstacle problem for semi-linear parabolic PDEs in which the non-linearity appears as the square of the gradient. Finally, we prove a comparison theorem for these obstacle problems when the generator is concave in the z$z$-variable.     

Parameter estimation and asymptotic stability in stochastic filtering

In this paper, we study the problem of estimating a Markov chain X$X$ (signal) from its noisy partial information Y$Y$, when the transition probability kernel depends on some unknown parameters. Our goal is to compute the conditional distribution process P{_Xn∣_Yn,…,_Y1}$\mathbb{P}\{X_n\mid Y_n,\dots ,Y_1\}$, referred to hereafter as the optimal filter. Following a standard Bayesian technique, we treat the parameters as a non-dynamic component of the Markov chain. As a result, the new Markov chain is not going to be mixing, even if the original one is. We show that, under certain conditions, the optimal filters are still going to be asymptotically stable with respect to the initial conditions. Thus, by computing the optimal filter of the new system, we can estimate the signal adaptively.     

Optimal acceptance rates for Metropolis algorithms: Moving beyond 0.234

Recent optimal scaling theory has produced a condition for the asymptotically optimal acceptance rate of Metropolis algorithms to be the well-known 0.234 when applied to certain multi-dimensional target distributions. These d$d$-dimensional target distributions are formed of independent components, each of which is scaled according to its own function of d$d$. We show that when the condition is not met the limiting process of the algorithm is altered, yielding an asymptotically optimal acceptance rate which might drastically differ from the usual 0.234. Specifically, we prove that as d→∞$d\to \infty$ the sequence of stochastic processes formed by say the i^∗$i^{\ast }$th component of each Markov chain usually converges to a Langevin diffusion process with a new speed measure υ$\upsilon$, except in particular cases where it converges to a one-dimensional Metropolis algorithm with acceptance rule α^∗${\alpha }^{\ast }$. We also discuss the use of inhomogeneous proposals, which might prove to be essential in specific cases.     

Stochastic processes with proportional increments and the last-arrival problem

The notion of stochastic processes with proportional increments is introduced. This notion is of general interest as indicated by its relationship with several stochastic processes, as counting processes, Lévy processes, and others, as well as martingales related with these processes. The focus of this article is on the motivation to introduce processes with proportional increments, as instigated by certain characteristics of stopping problems under weak information. We also study some general properties of such processes. These lead to new insights into the mechanism and characterization of Pascal processes. This again will motivate the introduction of more general f-increment processes as well as the analysis of their link with martingales. As a major application we solve the no-information version of the last-arrival problem   which was an open problem. Further applications deal with the impact of proportional increments on modelling investment problems, with a new proof of the 1/e$1/e$-law of best choice, and with other optimal stopping problems.     

Optimal impulse control for a multidimensional cash management system with generalized cost functions

We consider the optimal control of a multidimensional cash management system where the cash balances fluctuate as a homogeneous diffusion process in Rⁿ${\mathbb{R}}^n$. We formulate the model as an impulse control problem on an unbounded domain with unbounded cost functions. Under general assumptions we characterize the value function as a weak solution of a quasi-variational inequality in a weighted Sobolev space and we show the existence of an optimal policy. Moreover we prove the local uniform convergence of a finite element scheme to compute numerically the value function and the optimal cost. We compute the solution of the model in two-dimensions with linear and distance cost functions, showing what are the shapes of the optimal policies in these two simple cases. Finally our third numerical experiment computes the solution in the realistic case of the cash concentration of two bank accounts made by a centralized treasury.     

Duality theorem for the stochastic optimal control problem

We prove a duality theorem for the stochastic optimal control problem with a convex cost function and show that the minimizer satisfies a class of forward–backward stochastic differential equations. As an application, we give an approach, from the duality theorem, to h$h$-path processes for diffusion processes.     

Convergence of some time inhomogeneous Markov chains via spectral techniques

We consider the problem of giving explicit spectral bounds for time inhomogeneous Markov chains on a finite state space. We give bounds that apply when there exists a probability π$\pi$ such that each of the different steps corresponds to a nice ergodic Markov kernel with stationary measure π$\pi$. For instance, our results provide sharp bounds for models such as semi-random transpositions and semi-random insertions (in these cases π$\pi$ is the uniform probability on the symmetric group).     

A fast dual proximal gradient algorithm for convex minimization and applications

We consider the convex composite problem of minimizing the sum of a strongly convex function and a general extended valued convex function. We present a dual-based proximal gradient scheme for solving this problem. We show that although the rate of convergence of the dual objective function sequence converges to the optimal value with the rate O(1/k²)$O(1/k^2)$, the rate of convergence of the primal sequence is of the order O(1/k)$O(1/k)$.     

Multi-player stopping games with redistribution of payoffs and BSDEs with oblique reflection

We examine the connections between a novel class of multi-person stopping games with redistribution of payoffs and multi-dimensional reflected BSDEs in discrete- and continuous-time frameworks. Our goal is to provide an essential extension of classic results for two-player stopping games (Dynkin games) to the multi-player framework. We show the link between certain multi-period m$m$-player stopping games and a new kind of m$m$-dimensional reflected BSDEs. The existence and uniqueness of a solution to continuous-time reflected BSDEs are established. Continuous-time redistribution games are constructed with the help of reflected BSDEs and a characterization of the value of such stopping games is provided.     

A martingale decomposition for quadratic forms of Markov chains (with applications)

We develop a martingale-based decomposition for a general class of quadratic forms of Markov chains, which resembles the well-known Hoeffding decomposition of U$U$-statistics of i.i.d. data up to a reminder term. To illustrate the applicability of our results, we discuss how this decomposition may be used to studying the large-sample properties of certain statistics in two problems: (i) we examine the asymptotic behavior of lag-window estimators in time series, and (ii) we derive an asymptotic linear representation and limiting distribution of U$U$-statistics with varying kernels in time series. We also discuss simplified examples of interest in statistics and econometrics.     

Stochastic approximations of constrained discounted Markov decision processes

We consider a discrete-time constrained Markov decision process under the discounted cost optimality criterion. The state and action spaces are assumed to be Borel spaces, while the cost and constraint functions might be unbounded. We are interested in approximating numerically the optimal discounted constrained cost. To this end, we suppose that the transition kernel of the Markov decision process is absolutely continuous with respect to some probability measure μ  . Then, by solving the linear programming formulation of a constrained control problem related to the empirical probability measure _μn${\mu }_n$ of μ, we obtain the corresponding approximation of the optimal constrained cost. We derive a concentration inequality which gives bounds on the probability that the estimation error is larger than some given constant. This bound is shown to decrease exponentially in n. Our theoretical results are illustrated with a numerical application based on a stochastic version of the Beverton–Holt population model.     

Forward and reverse representations for Markov chains

In this paper we carry over the concept of reverse probabilistic representations developed in Milstein, Schoenmakers, Spokoiny [G.N. Milstein, J.G.M. Schoenmakers, V. Spokoiny, Transition density estimation for stochastic differential equations via forward–reverse representations, Bernoulli 10 (2) (2004) 281–312] for diffusion processes, to discrete time Markov chains. We outline the construction of reverse chains in several situations and apply this to processes which are connected with jump–diffusion models and finite state Markov chains. By combining forward and reverse representations we then construct transition density estimators for chains which have root-N$N$ accuracy in any dimension and consider some applications.