New Algorithm Addresses Markovian Bandits with Hidden States

This research delves into the problem of minimizing regret in Markovian bandits, specifically addressing scenarios where the underlying states are non-observable and decision epochs might be constrained. The focus is on a "pure" regret benchmark, comparing learning algorithm performance against an optimal pure policy that consistently selects the best arm. The authors introduce "self-degrading Markovian bandits," a generalization of rested Markovian bandits, where pure policies are asymptotically optimal. The study demonstrates that without prior knowledge of the bandit's structure, algorithms that rarely switch arms will inevitably incur super-logarithmic regret. Despite this, the researchers designed UCB-NOM, an optimistic algorithm inspired by UCB, which achieves nearly logarithmic regret. Furthermore, with prior knowledge, such as a bound on the bias functions of the arm, UCB-NOM can achieve O(log T) regret. The paper also provides a O(sqrt(T log T)) worst-case regret bound for UCB-NOM under this prior knowledge. Notably, the derived regret bounds are independent of the number of states in the underlying Markov chains, suggesting that non-observability of states is a relatively minor issue in self-degrading Markovian bandits.