Detecting an Odd Restless Markov Arm with a Trembling Hand

• URL: http://arxiv.org/abs/2005.06255v3
• Date: Thu, 31 Dec 2020 10:43:58 GMT
• Title: Detecting an Odd Restless Markov Arm with a Trembling Hand
• Authors: P. N. Karthik and Rajesh Sundaresan
• Abstract summary: We consider a multi-armed bandit in which each arm is a Markov process evolving on a finite state space. The transition probability matrix of one of the arms (the odd arm) is different from the common transition probability matrix of all other arms. A decision maker wishes to identify the odd arm as quickly as possible, while keeping the probability of decision error small.
• Score: 18.122816058828906
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we consider a multi-armed bandit in which each arm is a Markov process evolving on a finite state space. The state space is common across the arms, and the arms are independent of each other. The transition probability matrix of one of the arms (the odd arm) is different from the common transition probability matrix of all the other arms. A decision maker, who knows these transition probability matrices, wishes to identify the odd arm as quickly as possible, while keeping the probability of decision error small. To do so, the decision maker collects observations from the arms by pulling the arms in a sequential manner, one at each discrete time instant. However, the decision maker has a trembling hand, and the arm that is actually pulled at any given time differs, with a small probability, from the one he intended to pull. The observation at any given time is the arm that is actually pulled and its current state. The Markov processes of the unobserved arms continue to evolve. This makes the arms restless. For the above setting, we derive the first known asymptotic lower bound on the expected time required to identify the odd arm, where the asymptotics is of vanishing error probability. The continued evolution of each arm adds a new dimension to the problem, leading to a family of Markov decision problems (MDPs) on a countable state space. We then stitch together certain parameterised solutions to these MDPs and obtain a sequence of strategies whose expected times to identify the odd arm come arbitrarily close to the lower bound in the regime of vanishing error probability. Prior works dealt with independent and identically distributed (across time) arms and rested Markov arms, whereas our work deals with restless Markov arms.

Related papers

• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  We develop a general framework for clustering and distribution matching problems with bandit feedback. We derive a non-asymptotic lower bound on the average number of arm pulls for any online algorithm with an error probability not exceeding $delta$.
  arXiv  Detail & Related papers  (2024-09-08T12:19:12Z)
• Optimal Best Arm Identification with Fixed Confidence in Restless Bandits [66.700654953613]
  We study best arm identification in a restless multi-armed bandit setting with finitely many arms. The discrete-time data generated by each arm forms a homogeneous Markov chain taking values in a common, finite state space. It is demonstrated that tracking the long-term behavior of a certain Markov decision process and its state-action visitation proportions are the key ingredients in analyzing the converse and achievability bounds.
  arXiv  Detail & Related papers  (2023-10-20T10:04:05Z)
• Federated Best Arm Identification with Heterogeneous Clients [62.36929749450298]
  We study best arm identification in a federated multi-armed bandit setting with a central server and multiple clients. We show that for any algorithm whose upper bound on the expected stopping time matches with the lower bound up to a multiplicative constant (em almost-optimal algorithm) We propose a novel algorithm that communicates at exponential time instants, and demonstrate that it is almost-optimal.
  arXiv  Detail & Related papers  (2022-10-14T13:09:11Z)
• Almost Cost-Free Communication in Federated Best Arm Identification [76.12303738941254]
  We study the problem of best arm identification in a federated learning multi-armed bandit setup with a central server and multiple clients. We propose a novel algorithm sc FedElim that is based on successive elimination and communicates only in exponential time steps.
  arXiv  Detail & Related papers  (2022-08-19T08:37:09Z)
• Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
  We study the problem of identifying the best arm in a multi-armed bandit environment. A decision entity wishes to find the index of the best arm as quickly as possible, subject to an upper bound error probability. We show that this policy achieves an upper bound that depends on $R$ and is monotonically non-increasing as $Rtoinfty$.
  arXiv  Detail & Related papers  (2022-03-29T04:58:04Z)
• Restless Multi-Armed Bandits under Exogenous Global Markov Process [20.58296570065978]
  We consider an extension to the restless multi-armed bandit (RMAB) problem with unknown arm dynamics. Under each global state, the rewards process of each arm evolves according to an unknown Markovian rule. We develop the Learning under Exogenous Markov Process (LEMP) algorithm, that achieves a logarithmic regret order with time.
  arXiv  Detail & Related papers  (2022-02-28T10:29:42Z)
• Learning in Restless Bandits under Exogenous Global Markov Process [13.836565669337057]
  We consider an extension to the restless multi-armed bandit (RMAB) problem with unknown arm dynamics. Under each global state, the rewards process of each arm evolves according to an unknown Markovian rule. We develop the Learning under Exogenous Markov Process (LEMP) algorithm to minimize regret.
  arXiv  Detail & Related papers  (2021-12-17T12:47:30Z)
• Learning to Detect an Odd Restless Markov Arm with a Trembling Hand [12.467685221424032]
  anomaly means that the transition probability matrix of one of the arms is different from the common TPM of each of the non-odd arms. We devise a policy based on the principle of certainty equivalence, and demonstrate that under a continuous selection assumption and a certain regularity assumption on the TPMs, the policy achieves the lower bound arbitrarily closely. Our achievability analysis is based on resolving the identifiability problem in the context of a certain countable-state controlled Markov process.
  arXiv  Detail & Related papers  (2021-05-08T05:53:12Z)
• Online Model Selection: a Rested Bandit Formulation [49.69377391589057]
  We introduce and analyze a best arm identification problem in the rested bandit setting. We define a novel notion of regret for this problem, where we compare to the policy that always plays the arm having the smallest expected loss at the end of the game. Unlike known model selection efforts in the recent bandit literature, our algorithm exploits the specific structure of the problem to learn the unknown parameters of the expected loss function.
  arXiv  Detail & Related papers  (2020-12-07T08:23:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.