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.
This paper attempts to answer a question of "indexability" for simple Kalman filter, restless bandits. The context used is that of tracking N independent time-series, each of which follows a Gaussian random walk. At each time point (discrete time) an action is made to observe one of these time-series with higher precision than the others. The task is to choose the actions (or a policy producing the actions) which minimises a weighted sum of the error variances. The authors cast this problem as a multi-arm restless bandit and ask if previous work on "indexing" can be applied to it. The main result of the paper is to prove that the bandit is indexable under certain assumptions on the optimal policy.The first part of the paper lays out the problem as has just been described, as well as stating the main theorem of the paper. The authors do this with a reasonable amount of clarity. That said, some sentences could be written more clearly (e.g. the last sentence of the opening paragraph).The bulk of the paper is then made up of a proof of the main theorem. This involves the use of mathematical concepts which I suspect are relatively unknown amongst the community. The authors do a commendable job of trying to introduce all the definitions and lead the reader through the proof.While the result of the paper is interesting I feel the authors could have done more to explain why it is important. Clearly there is a significant limit on space due to the necessity of introducing the mathematical concepts, but there is nothing in the paper to tie the result back to the original context in which the problem was set.