Publications

2006

• Geometric Variance Reduction in Markov Chains: Application to Value Function and Gradient Estimation
  
  • Munos Rémi
  Journal of Machine Learning Research, Microtome Publishing, 2006, 7, pp.413-427. We study a variance reduction technique for Monte Carlo estimation of functionals in Markov chains. The method is based on designing sequential control variates using successive approximations of the function of interest V. Regular Monte Carlo estimates have a variance of O(1/N), where N is the number of sample trajectories of the Markov chain. Here, we obtain a geometric variance reduction O(ρ^N) (with ρ<1) up to a threshold that depends on the approximation error V-AV, where A is an approximation operator linear in the values. Thus, if V belongs to the right approximation space (i.e. AV=V), the variance decreases geometrically to zero. An immediate application is value function estimation in Markov chains, which may be used for policy evaluation in a policy iteration algorithm for solving Markov Decision Processes. Another important domain, for which variance reduction is highly needed, is gradient estimation, that is computing the sensitivity ∂αV of the performance measure V with respect to some parameter α of the transition probabilities. For example, in policy parametric optimization, computing an estimate of the policy gradient is required to perform a gradient optimization method. We show that, using two approximations for the value function and the gradient, a geometric variance reduction is also achieved, up to a threshold that depends on the approximation errors of both of those representations.
• Analysis of two linear sampling methods applied to electromagnetic imaging of buried objects
  
  • Cakoni Fioralba
  • Fares M'Barek
  • Haddar Houssem
  Inverse Problems, IOP Publishing, 2006, 22 (3), pp.845--867. (10.1088/0266-5611/22/3/007)
  DOI : 10.1088/0266-5611/22/3/007
• A Forward-Backward Stochastic Algorithm For Quasi-Linear PDEs
  
  • Delarue François
  • Menozzi Stéphane
  The Annals of Applied Probability, Institute of Mathematical Statistics (IMS), 2006, 16, pp.140-184. We propose a time-space discretization scheme for quasi-linear PDEs. The algorithm relies on the theory of fully coupled Forward-Backward SDEs, which provides an efficient probabilistic representation of this type of equations. The derivated algorithm holds for strong solutions defined on any interval of arbitrary length. As a bypass product, we obtain a discretization procedure for the underlying FBSDE.
• Discretization and simulation of the Zakai equation
  
  • Gobet Emmanuel
  • Pagès Gilles
  • Pham Huyên
  • Printems Jacques
  SIAM Journal on Numerical Analysis, Society for Industrial and Applied Mathematics, 2006, 44 (6), pp.2505-2538. This paper is concerned with numerical approximations for the stochastic partial differential Zakai equation of nonlinear filtering problems. The approximation scheme is based on the representation of the solutions as weighted conditional distributions. We first accurately analyze the error caused by an Euler-type scheme of time discretization. Sharp error bounds are calculated: we show that the rate of convergence is in general of order √δ (δ is the time step), but in the case when there is no correlation between the signal and the observation for the Zakai equation, the order of convergence becomes δ. This result is obtained by carefully employing techniques of Malliavin calculus. In a second step, we propose a simulation of the time discretization Euler scheme by a quantization approach. Formally, this consists in an approximation of the weighted conditional distribution by a conditional discrete distribution on finite supports. We provide error bounds and rate of convergence in terms of the number N of the grids of this support. These errors are minimal at some optimal grids which are computed by a recursive method based on Monte Carlo simulations. Finally, we illustrate our results with some numerical experiments arising from a correlated Kalman–Bucy filter. (10.1137/050623140)
  DOI : 10.1137/050623140
• Homogenization of the Schrodinger equation with a time oscillating potential
  
  • Allaire Grégoire
  • Vanninathan Muthusamy
  Discrete and Continuous Dynamical Systems - Series B, American Institute of Mathematical Sciences, 2006, 6, pp.1-16. We study the homogenization of a Schrodinger equation in a periodic medium with a time dependent potential. This is a model for semiconductors excited by an external electromagnetic wave. We prove that, for a suitable choice of oscillating (both in time and space) potential, one can partially transfer electrons from one Bloch band to another. This justifies the famous "Fermi golden rule" for the transition probability between two such states which is at the basis of various optical properties of semiconductors. Our method is based on a combination of classical homogenization techniques (two-scale convergence and suitable oscillating test functions) and of Bloch waves theory.
• Convex Sobolev inequalities and spectral gap
  
  • Dolbeault Jean
  • Bartier Jean-Philippe
  Comptes Rendus. Mathématique, Académie des sciences (Paris), 2006, 342 (5), pp.307-312. This note is devoted to the proof of convex Sobolev (or generalized Poincaré) inequalities which interpolate between spectral gap (or Poincaré) inequalities and logarithmic Sobolev inequalities. We extend to the whole family of convex Sobolev inequalities results which have recently been obtained by Cattiaux and Carlen and Loss for logarithmic Sobolev inequalities. Under local conditions on the density of the measure with respect to a reference measure, we prove that spectral gap inequalities imply all convex Sobolev inequalities with constants which are uniformly bounded in the limit approaching the logarithmic Sobolev inequalities. We recover the case of the logarithmic Sobolev inequalities as a special case.
• Modification of UCT with Patterns in Monte-Carlo Go
  
  • Gelly Sylvain
  • Wang Yizao
  • Munos Rémi
  • Teytaud Olivier
  , 2006. Algorithm UCB1 for multi-armed bandit problem has already been extended to Algorithm UCT (Upper bound Confidence for Tree) which works for minimax tree search. We have developed a Monte-Carlo Go program, MoGo, which is the first computer Go program using UCT. We explain our modification of UCT for Go application and also the intelligent random simulation with patterns which has improved significantly the performance of MoGo. UCT combined with pruning techniques for large Go board is discussed, as well as parallelization of UCT. MoGo is now a top level Go program on $9\times9$ and $13\times13$ Go boards.
• Model uncertainty and its impact on the pricing of derivative instruments
  
  • Cont Rama
  Mathematical Finance, Wiley, 2006, 16 (3), pp.519 - 547. Model uncertainty, in the context of derivative pricing, can be defined as the uncertainty on the value of a contingent claim resulting from the lack of precise knowledge of the pricing model to be used for its valuation. We introduce here a quantitative framework for defining model uncertainty in option pricing models. After discussing some properties which a quantitative measure of model uncertainty should verify in order to be useful and relevant in the context of risk measurement and management, we propose a method for measuring model uncertainty which verifies these properties and yields numbers which are comparable to other risk measures and compatible with observations of market prices of a set of benchmark derivatives. We illustrate the difference between model uncertainty and the more common notion of "market risk" through examples. Finally, we illustrate the connection between our proposed measure of model uncertainty and the recent literature on coherent and convex risk measures. (10.1111/j.1467-9965.2006.00281.x)
  DOI : 10.1111/j.1467-9965.2006.00281.x
• A New Domain Decomposition Method for the Compressible Euler Equations
  
  • Dolean Victorita
  • Nataf Frédéric
  ESAIM: Mathematical Modelling and Numerical Analysis, Société de Mathématiques Appliquées et Industrielles (SMAI) / EDP, 2006, 40 (4), pp.689-703. In this work we design a new domain decomposition method for the Euler equations in 2 dimensions. The basis is the equivalence via the Smith factorization with a third order scalar equation to whom we can apply an algorithm inspired from the Robin-Robin preconditioner for the convection-diffusion equation. Afterwards we translate it into an algorithm for the initial system and prove that at the continuous level and for a decomposition into 2 sub-domains, it converges in 2 iterations. This property cannot be preserved strictly at discrete level and for arbitrary domain decompositions but we still have numerical results which confirm a very good stability with respect to the various parameters of the problem (mesh size, Mach number, ....).
• Deviation bounds for additive functionals of Markov processes
  
  • Cattiaux Patrick
  • Guillin Arnaud
  , 2006. In this paper we derive non asymptotic deviation bounds for $$\P_\nu (|\frac 1t \int_0^t V(X_s) ds - \int V d\mu | \geq R)$$ where $X$ is a $\mu$ stationary and ergodic Markov process and $V$ is some $\mu$ integrable function. These bounds are obtained under various moments assumptions for $V$, and various regularity assumptions for $\mu$. Regularity means here that $\mu$ may satisfy various functional inequalities (F-Sobolev, generalized Poincaré etc...).
• Subgeometric ergodicity of Markov chains
  
  • Douc Randal
  • Moulines Eric
  • Soulier Philippe
  , 2006, pp.55--64. The goal of this paper is to give a short and self contained proof of general bounds for subgeometric rates of convergence, under practical conditions. The main result whose proof, based on coupling, provides an intuitive understanding of the results of Nummelin and Tuominen (1983) and Tuominen and Tweedie (1994). To obtain practical rates, a very general drift condition, recently introduced in Douc et al (2004) is used.
• High Order Generalized Impedance Boundary Conditions in Electromagnetic Scattering Problems
  
  • Duruflé Marc
  • Haddar Houssem
  • Joly Patrick
  Comptes Rendus. Physique, Académie des sciences (Paris), 2006, 7, pp.533-542. We briefly review the use and the derivation of Generalized Impedance Boundary Conditions (GIBC) in the case of thin dielectric coating and in the case of strongly absorbing medium, within the context of electromagnetic scattering problem at a fixed frequency. We then numerically test the validity and accuracy of these boundary conditions in the case of high absorption. A numerical treatment of the corner singularity is proposed to recover the accuracy of the GIBC for singular geometries.
• Weak and Strong Order of Convergence of a Semidiscrete Scheme for the Stochastic Nonlinear Schrodinger Equation
  
  • de Bouard Anne
  • Debussche Arnaud
  Applied Mathematics and Optimization, Springer Verlag (Germany), 2006, 54 (3), pp.369-399. In this article we analyze the error of a semidiscrete scheme for the stochastic nonlinear Schrodinger equation with power nonlinearity. We consider supercritical or subcritical nonlinearity and the equation can be either focusing or defocusing. Allowing sufficient spatial regularity we prove that the numerical scheme has strong order in general and order 1 if the noise is additive. Furthermore, we also prove that the weak order is always 1 (10.1007/s00245-006-0875-0)
  DOI : 10.1007/s00245-006-0875-0
• Policy Gradient in Continuous Time
  
  • Munos Rémi
  Journal of Machine Learning Research, Microtome Publishing, 2006, 7, pp.771-791. Policy search is a method for approximately solving an optimal control problem by performing a parametric optimization search in a given class of parameterized policies. In order to process a local optimization technique, such as a gradient method, we wish to evaluate the sensitivity of the performance measure with respect to the policy parameters, the so-called policy gradient. This paper is concerned with the estimation of the policy gradient for continuous-time, deterministic state dynamics, in a reinforcement learning framework, that is, when the decision maker does not have a model of the state dynamics. We show that usual likelihood ratio methods used in discrete-time, fail to proceed the gradient because they are subject to variance explosion when the discretization time-step decreases to 0. We describe an alternative approach based on the approximation of the pathwise derivative, which leads to a policy gradient estimate that converges almost surely to the true gradient when the time-step tends to 0. The underlying idea starts with the derivation of an explicit representation of the policy gradient using pathwise derivation. This derivation makes use of the knowledge of the state dynamics. Then, in order to estimate the gradient from the observable data only, we use a stochastic policy to discretize the continuous deterministic system into a stochastic discrete process, which enables to replace the unknown coefficients by quantities that solely depend on known data. We prove the almost sure convergence of this estimate to the true policy gradient when the discretization time-step goes to zero. The method is illustrated on two target problems, in discrete and continuous control spaces.
• The dressed mobile atoms and ions
  
  • Amour Laurent
  • Grébert Benoît
  • Guillot Jean-Claude
  Journal de Mathématiques Pures et Appliquées, Elsevier, 2006, 86, pp.177-200. We consider free atoms and ions in $\R^3$ interacting with the quantized electromagnetic field. Because of the translation invariance we consider the reduced hamiltonian associated with the total momentum. After introducing an ultraviolet cutoff we prove that the reduced hamiltonian for atoms has a ground state if the coupling constant and the total momentum are sufficiently small. In the case of ions an extra infrared regularization is needed. We also consider the case of the hydrogen atom in a constant magnetic field. Finally we determine the absolutely continuous spectrum of the reduced hamiltonian.
• A new linear sampling method for the electromagnetic imagining of buried objects
  
  • Cakoni Fioralba
  • Haddar Houssem
  , 2006, pp.19--30. We present a new linear sampling method for determining the shape of scattering objects imbedded in a known inhomogeneous medium from a knowledge of the scattered electromagnetic field due to a point source incident field at fixed frequency. The method does not require any a prior information on the physical properties of the scattering object and, under some restrictions, avoids the need to compute the Green's tensor for the background medium. (10.1142/9789812773197_0003)
  DOI : 10.1142/9789812773197_0003