On Gittins’ index theorem in continuous time

We give a new and comparably short proof of Gittins’ index theorem for dynamic allocation problems of the multi-armed bandit type in continuous time under minimal assumptions. This proof gives a complete characterization of optimal allocation strategies as those policies which follow the current leader among the Gittins indices while ensuring that a Gittins index is at an all-time low whenever the associated project is not worked on exclusively. The main tool is a representation property of Gittins index processes which allows us to show that these processes can be chosen to be pathwise lower semi-continuous from the right and quasi-lower semi-continuous from the left. Both regularity properties turn out to be crucial for our characterization and the construction of optimal allocation policies.     

Multi-armed bandits with simple arms

An exact solution to certain multi-armed bandit problems with independent and simple arms is presented. An arm is simple if the observations associated with the arm have one of two distributions conditional on the value of an unknown dichotomous parameter. This solution is obtained relating Gittins indices for the arms to ladder variables for associated random walks.     

Reflections on a New Approach to Gittins Indexation

Traditional approaches to stochastic resource allocation problems (including the classical multi-armed bandit problems) have usually made use of dynamic programming (DP) methodology, perhaps buttressed by further ad hoc arguments. While such approaches seem ‘natural’ they have usually proved technically very difficult. Bertsimas and Niño-Mora have recently given a radically new account of many important results in this area which relate to Gittins indices. The key to their approach is in the characterisation of the region of achievable performance. The optimisation problems of interest are then solved as linear programs over this region. Here we exploit elements within the Bertsimas and Niño-Mora framework (in particular, its capacity to give formulae for the total return of a given policy in closed form) to obtain (i) a simple dynamic programming proof of the optimality of Gittins index policies and (ii) a range of index-based suboptimality bounds for general policies for a variety of stochastic models for resource allocation.     

Optimal decision indices for R&D project evaluation in the pharmaceutical industry: Pearson index versus Gittins index

This paper examines issues related to various decision-based analytic approaches to sequential choice of projects, with special motivation from and application in the pharmaceutical industry. In particular, the Pearson index and Gittins index are considered as key strategic decision-making tools for the selection of R&D projects. It presents a proof of optimality of the Pearson index based on the Neyman–Pearson lemma. Emphasis is also given to how a project manager may differentiate between the two indices based on concepts from statistical decision theory. This work demonstrates and justifies the correct use of the Pearson index.     

A general rapid network design,line planning and fleet investment integrated model

We study four proofs that the Gittins index priority rule is optimal for alternative bandit processes. These include Gittins’ original exchange argument, Weber’s prevailing charge argument, Whittle’s Lagrangian dual approach, and Bertsimas and Niño-Mora’s proof based on the achievable region approach and generalized conservation laws. We extend the achievable region proof to infinite countable state spaces, by using infinite dimensional linear programming theory.     

Approximate valuation of average options

This paper concerns the valuation of average options of European type where an investor has the right to buy the average of an asset price process over some time interval, as the terminal price, at a prespecified exercise price. A discrete model is first constructed and a recurrence formula is derived for the exact price of the discrete average call option. For the continuous average call option price, we derive some approximations and theoretical upper and lower bounds. These approximations are shown to be very accurate for at-the-money and in-the-money cases compared to the simulation results. The theoretical bounds can be used to provide useful information in pricing average options.     

On the Gittins index in the M/G/1 queue

For an M/G/1 queue with the objective of minimizing the mean number of jobs in the system, the Gittins index rule is known to be optimal among the set of non-anticipating policies. We develop properties of the Gittins index. For a single-class queue it is known that when the service time distribution is of type Decreasing Hazard Rate (New Better than Used in Expectation), the Foreground–Background (First-Come-First-Served) discipline is optimal. By utilizing the Gittins index approach, we show that in fact, Foreground–Background and First-Come-First-Served are optimal if and only if the service time distribution is of type Decreasing Hazard Rate and New Better than Used in Expectation, respectively. For the multi-class case, where jobs of different classes have different service distributions, we obtain new results that characterize the optimal policy under various assumptions on the service time distributions. We also investigate distributions whose hazard rate and mean residual lifetime are not monotonic.     

One-armed bandit models with continuous and delayed responses

One-armed bandit processes with continuous delayed responses are formulated as controlled stochastic processes following the Bayesian approach. It is shown that under some regularity conditions, a Gittins-like index exists which is the limit of a monotonic sequence of break-even values characterizing optimal initial selections of arms for finite horizon bandit processes. Furthermore, there is an optimal stopping solution when all observations on the unknown arm are complete. Results are illustrated with a bandit model having exponentially distributed responses, in which case the controlled stochastic process becomes a Markov decision process, the Gittins-like index is the Gittins index and the Gittins index strategy is optimal. Acknowledgement.We thank an anonymous referee for constructive and insightful comments, especially those related to the notion of the Gittins index.Both authors are funded by the Natural Sciences and Engineering Research Council (NSERC) of Canada.     

Termination Criteria for Linear Problems

We study two termination criteria which are used in computational practice. They are analyzed for linear problems in the average case setting. It is assumed that arbitrary continuous linear functionals can be computed and consecutive approximations are chosen in the best possible way. The first termination criterion is satisfied if the difference between two consecutive approximations becomes less than a certain bound τ. We prove that the first termination criterion gives satisfactory results only for some cases. The second termination criterion is satisfied if two consecutive differences between consecutive approximations become less than τ. We prove that the second termination criterion gives satisfactory results for all cases.     

An infinite-time relaxation theorem for differential inclusions

The fundamental relaxation result for Lipschitz differential inclusions is the Filippov-Wazewski Relaxation Theorem, which provides approximations of trajectories of a relaxed inclusion on finite intervals. A complementary result is presented, which provides approximations on infinite intervals, but does not guarantee that the approximation and the reference trajectory satisfy the same initial condition.

     

Convergence of quasi-Newton matrices generated by the symmetric rank one update

Quasi-Newton algorithms for unconstrained nonlinear minimization generate a sequence of matrices that can be considered as approximations of the objective function second derivatives. This paper gives conditions under which these approximations can be proved to converge globally to the true Hessian matrix, in the case where the Symmetric Rank One update formula is used. The rate of convergence is also examined and proven to be improving with the rate of convergence of the underlying iterates. The theory is confirmed by some numerical experiments that also show the convergence of the Hessian approximations to be substantially slower for other known quasi-Newton formulae.The work of this author was supported by the National Sciences and Engineering Research Council of Canada, and by the Information Technology Research Centre, which is funded by the Province of Ontario.     

Correcting Jaccard and other similarity indices for chance agreement in cluster analysis

Correcting a similarity index for chance agreement requires computing its expectation under fixed marginal totals of a matching counts matrix. For some indices, such as Jaccard, Rogers and Tanimoto, Sokal and Sneath, and Gower and Legendre the expectations cannot be easily found. We show how such similarity indices can be expressed as functions of other indices and expectations found by approximations such that approximate correction is possible. A second approach is based on Taylor series expansion. A simulation study illustrates the effectiveness of the resulting correction of similarity indices using structured and unstructured data generated from bivariate normal distributions.     

Approximate inversion of the Black–Scholes formula using rational functions

The Black–Scholes formula is often used in the backward direction to invert the implied volatility, usually with some solver method. Solver methods, being aesthetically unappealing, are also slower than closed-form approximations. However, closed-form approximations in previous works lack accuracy, often providing option pricing errors well exceeding the bid–ask spreads. We develop a new closed-form method based on the rational approximation. The rational approximation is much faster than typical solver methods and very accurate for both at-the-money and away-from-the-money options. Its accuracy can be further improved by one or two steps of Newton–Raphson iterations.     

Error estimates for approximate approximations with Gaussian kernels on compact intervals

The aim of this paper is the investigation of the error which results from the method of approximate approximations applied to functions defined on compact intervals, only. This method, which is based on an approximate partition of unity, was introduced by Maz’ya in 1991 and has mainly been used for functions defined on the whole space up to now. For the treatment of differential equations and boundary integral equations, however, an efficient approximation procedure on compact intervals is needed.In the present paper we apply the method of approximate approximations to functions which are defined on compact intervals. In contrast to the whole space case here a truncation error has to be controlled in addition. For the resulting total error pointwise estimates and L₁-estimates are given, where all the constants are determined explicitly.     

Generalized Cornish-Fisher expansions

Cornish-Fisher expansions about the normal distribution provide accurate approximations for distributions of estimates and also for the level in the nominal error of confidence intervals. However, there is an advantage is expanding about a skew distribution like the chi-square, since the first order approximations become second order if the skewness is matched. Higher order approximations are also simplified. We demonstrate the method by approximating the distribution of standardized and Studentized linear combinations of means.     

Callable risky perpetual debt with protection period

Issuances in the USD 260 Bn global market of perpetual risky debt are often motivated by capital requirements for financial institutions. We analyze callable risky perpetual debt emphasizing an initial protection (‘grace’) period before the debt may be called. The total market value of debt including the call option is expressed as a portfolio of perpetual debt and barrier options with a time dependent barrier. We also analyze how an issuer’s optimal bankruptcy decision is affected by the existence of the call option by using closed-form approximations. The model quantifies the increased coupon and the decreased initial bankruptcy level caused by the embedded option. Examples indicate that our closed form model produces reasonably precise coupon rates compared to numerical solutions. The credit-spread produced by our model is in a realistic order of magnitude compared to market data.     

Rationale Tschebyscheff-Approximation über unbeschränkten Intervallen

Summary We consider rational best approximations to functions real-valued and continuous on closed unbounded intervals of the extended real numbers. The error of the best approximation is characterized by an alternant, whose length may be different from the well-known number for a bounded interval. Besides some exceptional cases the best approximation is unique.     

The inertia of the symmetric approximation for low-rank matrices

In many areas of applied linear algebra, it is necessary to work with matrix approximations. A usual situation occurs when a matrix obtained from experimental or simulated data is needed to be approximated by a matrix that lies in a corresponding statistical model and satisfies some specific properties. In this short note, we focus on symmetric and positive-semidefinite approximations and we show that the positive and negative indices of inertia of the symmetric approximation and the rank of the positive-semidefinite approximation are always bounded from above by the rank of the original matrix.     

Richter’s local limit theorem and Black–Scholes type formulas

We prove a Black–Scholes type formula when the geometric Brownian motion originates from approximations by multinomial distributions. It is shown that the variance appearing in the Black–Scholes formula for option pricing can be structured according to occurrences of different types of events at each time instance using a local limit theorem for multinomial distributions in Richter (1956). The general approach has first been developed in Kan (2005).