The Dependent Doors Problem: An Investigation into Sequential Decisions
  without Feedback
  We introduce the dependent doors problem as an abstraction for situations in
which one must perform a sequence of possibly dependent decisions, without
receiving feedback information on the effectiveness of previously made actions.
Informally, the problem considers a set of $d$ doors that are initially closed,
and the aim is to open all of them as fast as possible. To open a door, the
algorithm knocks on it and it might open or not according to some probability
distribution. This distribution may depend on which other doors are currently
open, as well as on which other doors were open during each of the previous
knocks on that door. The algorithm aims to minimize the expected time until all
doors open. Crucially, it must act at any time without knowing whether or which
other doors have already opened. In this work, we focus on scenarios where
dependencies between doors are both positively correlated and acyclic.The
fundamental distribution of a door describes the probability it opens in the
best of conditions (with respect to other doors being open or closed). We show
that if in two configurations of $d$ doors corresponding doors share the same
fundamental distribution, then these configurations have the same optimal
running time up to a universal constant, no matter what are the dependencies
between doors and what are the distributions. We also identify algorithms that
are optimal up to a universal constant factor. For the case in which all doors
share the same fundamental distribution we additionally provide a simpler
algorithm, and a formula to calculate its running time. We furthermore analyse
the price of lacking feedback for several configurations governed by standard
fundamental distributions. In particular, we show that the price is logarithmic
in $d$ for memoryless doors, but can potentially grow to be linear in $d$ for
other distributions.We then turn our attention to investigate precise bounds.
Even for the case of two doors, identifying the optimal sequence is an
intriguing combinatorial question. Here, we study the case of two cascading
memoryless doors. That is, the first door opens on each knock independently
with probability $p\_1$. The second door can only open if the first door is
open, in which case it will open on each knock independently with probability
$p\_2$. We solve this problem almost completely by identifying algorithms that
are optimal up to an additive term of 1.
