A decision maker records measurements of a finite-state Markov chain corrupted by noise. The goal is to decide when the Markov chain hits a specific target state. The decision maker can choose from a finite set of sampling intervals to pick the next time to look at the Markov chain. The aim is to optimize an objective comprising of false alarm, delay cost and cumulative measurement sampling cost. Taking more frequent measurements yields accurate estimates but incurs a higher measurement cost. Making an erroneous decision too soon incurs a false alarm penalty. Waiting too long to declare the target state incurs a delay penalty. What is the optimal sequential strategy for the decision maker? The paper shows that under reasonable conditions, the optimal strategy has the following intuitive structure: when the Bayesian estimate (posterior distribution) of the Markov chain is away from the target state, look less frequently; while if the posterior is close to the target state, look more frequently. Bounds are derived for the optimal strategy. Also the achievable optimal cost of the sequential detector as a function of transition dynamics and observation distribution is analyzed. The sensitivity of the optimal achievable cost to parameter variations is bounded in terms of the Kullback divergence. To prove the results in this paper, novel stochastic dominance results on the Bayesian filtering recursion are derived. The formulation in this paper generalizes quickest time change detection to consider optimal sampling and also yields useful results in sensor scheduling (active sensing).
This paper analyzes the structure of the optimal sampling strategy of the decision-maker. The problem is an instance of a partially observed Markov decision process (POMDP) @cite_12 . In general, solving POMDPs and therefore determining the optimal strategy is computationally intractable (PSPACE hard @cite_1 ). However, returning to the example considered above, intuition suggests that the following strategy would be sensible (recall that the action set @math ): The key point is that such a strategy (choice of sampling interval @math ) is monotonically decreasing as the posterior distribution gets closer to the target state. By using stochastic dominance and lattice programming analysis, this paper shows that under reasonable conditions, the optimal sampling strategy always has this monotone structure. Lattice programming was championed by @cite_4 and provides a general set of sufficient conditions for the existence of monotone strategies in stochastic control problems. This area falls under the general umbrella of monotone comparative statics that has witnessed remarkable interest in the area of economics @cite_23 . Our results apply to general observation distributions (Gaussians, exponentials, Markov modulated Poisson, discrete memoryless channels, etc) and multi-state Markov chains.
@cite_23 @cite_4 @cite_1 @cite_12
2171212676 2911793117 2808915486 2040774021
This paper focuses on a continuous-time, continuous-space formulation of the stochastic optimal control problem with nonlinear dynamics and observation noise. We lay the mathematical foundations to construct, via incremental sampling, an approximating sequence of discrete-time finite-state partially observable Markov decision processes (POMDPs), such that the behavior of successive approximations converges to the behavior of the original continuous system in an appropriate sense. We also show that the optimal cost function and control policies for these POMDP approximations converge almost surely to their counterparts for the underlying continuous system in the limit. We demonstrate this approach on two popular continuous-time problems, viz., the Linear-Quadratic-Gaussian (LQG) control problem and the light-dark domain problem. Consider a Markov decision process (MDP) that admits a set of state-action features, which can linearly express the process's probabilistic transition model. We propose a parametric Q-learning algorithm that finds an approximate-optimal policy using a sample size proportional to the feature dimension @math and invariant with respect to the size of the state space. To further improve its sample efficiency, we exploit the monotonicity property and intrinsic noise structure of the Bellman operator, provided the existence of anchor state-actions that imply implicit non-negativity in the feature space. We augment the algorithm using techniques of variance reduction, monotonicity preservation, and confidence bounds. It is proved to find a policy which is @math -optimal from any initial state with high probability using @math sample transitions for arbitrarily large-scale MDP with a discount factor @math . A matching information-theoretical lower bound is proved, confirming the sample optimality of the proposed method with respect to all parameters (up to polylog factors). The partially observable Markov decision process (POMDP) provides a principled general framework for robot planning under uncertainty. Leveraging the idea of Monte Carlo sampling, recent POMDP planning algorithms have scaled up to various challenging robotic tasks, including, real-time online planning for autonomous vehicles. To further improve online planning performance, this paper presents IS-DESPOT, which introduces importance sampling to DESPOT, a state-of-the-art sampling-based POMDP algorithm for planning under uncertainty. Importance sampling improves DESPOT’s performance when there are critical, but rare events, which are difficult to sample. We prove that IS-DESPOT retains the theoretical guarantee of DESPOT. We demonstrate empirically that importance sampling significantly improves the performance of online POMDP planning for suitable tasks. We also present a general method for learning the importance sampling distribution. The restless bandit problem is one of the most well-studied generalizations of the celebrated stochastic multi-armed bandit (MAB) problem in decision theory. In its ultimate generality, the restless bandit problem is known to be PSPACE-Hard to approximate to any nontrivial factor, and little progress has been made on this problem despite its significance in modeling activity allocation under uncertainty. In this article, we consider the Feedback MAB problem, where the reward obtained by playing each of n independent arms varies according to an underlying on off Markov process whose exact state is only revealed when the arm is played. The goal is to design a policy for playing the arms in order to maximize the infinite horizon time average expected reward. This problem is also an instance of a Partially Observable Markov Decision Process (POMDP), and is widely studied in wireless scheduling and unmanned aerial vehicle (UAV) routing. Unlike the stochastic MAB problem, the Feedback MAB problem does not admit to greedy index-based optimal policies. We develop a novel duality-based algorithmic technique that yields a surprisingly simple and intuitive (2+e)-approximate greedy policy to this problem. We show that both in terms of approximation factor and computational efficiency, our policy is closely related to the Whittle index, which is widely used for its simplicity and efficiency of computation. Subsequently we define a multi-state generalization, that we term Monotone bandits, which remains subclass of the restless bandit problem. We show that our policy remains a 2-approximation in this setting, and further, our technique is robust enough to incorporate various side-constraints such as blocking plays, switching costs, and even models where determining the state of an arm is a separate operation from playing it. Our technique is also of independent interest for other restless bandit problems, and we provide an example in nonpreemptive machine replenishment. Interestingly, in this case, our policy provides a constant factor guarantee, whereas the Whittle index is provably polynomially worse. By presenting the first O(1) approximations for nontrivial instances of restless bandits as well as of POMDPs, our work initiates the study of approximation algorithms in both these contexts.