When are Kalman-filter restless bandits indexable?
We study the restless bandit associated with an extremely simple scalar Kalman filter model in discrete time. Under certain assumptions, we prove that the problem is indexable in the sense that the Whittle index is a non-decreasing function of the relevant belief state. In spite of the long history of this problem, this appears to be the first such proof. We use results about Schur-convexity and mechanical words, which are particular binary strings intimately related to palindromes.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Simulation Based Algorithms for Markov Decision Processes and Multi-Action Restless Bandits
We consider multi-dimensional Markov decision processes and formulate a long term discounted reward optimization problem. Two simulation based algorithms---Monte Carlo rollout policy and parallel rollout policy are studi…
Indexability of Finite State Restless Multi-Armed Bandit and Rollout Policy
We consider finite state restless multi-armed bandit problem. The decision maker can act on M bandits out of N bandits in each time step. The play of arm (active arm) yields state dependent rewards based on action and wh…
Conditions for indexability of restless bandits and an O(K^3) algorithm to compute Whittle index
Restless bandits are a class of sequential resource allocation problems concerned with allocating one or more resources among several alternative processes where the evolution of the process depends on the resource alloc…
Two families of indexable partially observable restless bandits and Whittle index computation
We consider the restless bandits with general state space under partial observability with two observational models: first, the state of each bandit is not observable at all, and second, the state of each bandit is obser…
GINO-Q: Learning an Asymptotically Optimal Index Policy for Restless Multi-armed Bandits
The restless multi-armed bandit (RMAB) framework is a popular model with applications across a wide variety of fields. However, its solution is hindered by the exponentially growing state space (with respect to the numbe…
Multi-Armed BanditsQ-Learning