| dc.description.abstract | This thesis deals with several closely related, but subtly di erent problems in the area
of sequential stochastic optimisation. A joint property they share is the online constraint
that is imposed on the decision-maker: once she observes an element, the decision
whether to accept or reject it should be made immediately, without an option to
recall the element in future. Observations in these problems are random variables, which
take values in either R or in Rd, following known reasonably well-behaving continuous
distributions.
The stochastic nature of observations and the online condition shape the optimal selection
policy. Furthermore, the latter indeed depends on the latest information and is
updated at every step. The optimal policies may not be easily described. Even for a
small number of steps, solving the optimality recursion may be computationally demanding.
However, a detailed investigation yields a range of easily-constructible suboptimal
policies that asymptotically perform as well as the optimal one. We aim to describe both
optimal and suboptimal policies and study properties of the random processes that arise
naturally in these problems.
Speci cally, in this thesis we focus on the sequential selection of the longest increasing
subsequence in discrete and continuous time introduced by Samuels and Steele [55], the
quickest sequential selection of the increasing subsequence of a xed size recently studied
by Arlotto et al. [3], and the sequential selection under a sum constraint introduced by
Co man et al. [26]. | en_US |
