We propose an asymptotically optimal heuristic, which we term randomized assignment control (RAC) for a restless multi-armed bandit problem with discrete-time and finite states. It is constructed using a linear programming relaxation of the original stochastic control formulation. In contrast to most of the existing literature, we consider a finite-horizon problem with multiple actions and time-dependent (i.e. nonstationary) upper bound on the number of bandits that can be activated at each time period; indeed, our analysis can also be applied in the setting with nonstationary transition matrix and nonstationary cost function. The asymptotic setting is obtained by letting the number of bandits and other related parameters grow to infinity. Our main contribution is that the asymptotic optimality of RAC in this general setting does not require indexability properties or the usual stability conditions of the underlying Markov chain (e.g. unichain) or fluid approximation (e.g. global stable attractor). Moreover, our multi-action setting is not restricted to the usual dominant action concept. Finally, we show that RAC is also asymptotically optimal for a dynamic population, where bandits can randomly arrive and depart the system.

The Vardi casino with parameter 0 < c < 1 consists of infinitely many tables indexed by their odds, each of which returns the same (negative) expected winnings -c per dollar. A gambler seeks to maximize the probability of reaching a fixed fortune by gambling repeatedly with suitably chosen stakes and tables (odds). The optimal strategy is derived explicitly subject to the constraint that the gambler is allowed to play only a given finite number of times. Some properties of the optimal strategy are also discussed.

It is shown by a simple sample path argument that the ruin probabilities for a risk reserve process with premium rate p(r) depending on the reserve r and finite or infinite horizon are related in a simple way to the state probabilities of a compound Poisson dam with the same release rate p(r) at content r. In the infinite horizon case, this result has been established by Harrison and Resnick (1978), and in the finite horizon case with constant p it extends well-known relations to the M/G/1 virtual waiting time.