A control problem arising in the sequential design of experiments (Q1080274)

A random walk \(\{W_ n\}\) in the plane starts from some initial point \(x_ 0\) not in the first quadrant \({\mathcal Q}_+\). At each step a distribution function for its increments is chosen between the pair \(\{F_ 1,F_ 2\}\) in a nonanticipative way. Suppose their mean vectors \(\mu_ 1\) and \(\mu_ 2\) are such that \[ \mu_ 1^{(1)}>\mu_ 2^{(1)}\geq 0\quad \mu_ 2^{(2)}>\mu_ 1^{(2)}\geq 0. \] Then the policy which chooses \(F_ 2(F_ 1)\) when the current position of \(\{W_ n\}\) is above (below) a straight line belonging to the cone generated by \(\mu_ 1\) and \(\mu_ 2\) is suboptimal in the following sense. The excess of mean time to reach \({\mathcal Q}_+\) over the optimal time is bounded by a constant independent of \(x_ 0.\) A more general problem arising in the sequential design of experiments is discussed in which the state space is \({\mathbb{R}}^ d\) and the law of the increments is chosen among d alternatives \(\{F_ i\}\) incurring in corresponding costs \(\{d_ i\}\). The following class of control policies is considered. Let r(x) be the distance of x from the diagonal (i.e. span(1,...,1)). A policy is called diagonal stabilizing (DS(\(\alpha\) ;r)) if there exists \(\alpha >0\) and \(r<\infty\) such that wherever \(| r(W_ n)| >r\) then the mean \(\mu_{n+1}\) of the chosen distribution is such that \((\mu,r(W_ n))\geq \alpha | r(W_ n)|.\) Under conditions on the mean vectors analogous to the above ones, it is proved that the difference between the cost attached to any such policy and the optimal nonanticipative one is bounded by a constant for all initial points \(x_ 0\) such that \(r(x_ 0)\leq r\). For such a particular problem such results considerably improve the results obtained by \textit{H. Chernoff} [Ann. Math. Stat. 30, 755-770 (1959; Zbl 0092.361)] about the asymptotic efficiency of suboptimal policies in the sequential design of experiments. The proofs make essential use of stochastic comparison arguments.