Kaan Buyukkalayci

Kaan Buyukkalayci, Kyle Pak, Merve Karakas et al.

We study set-valued decision rules in which performance is defined by the inclusion of the top-$p$ hypotheses, rather than only the single best or true hypothesis. This criterion is motivated by sensor selection for target tracking, where inexpensive measurements are used to identify a list of sensor nodes that are likely to be closest to a target. We analyze the performance of top-$p$ versus top-$1$ selection under sequential hypothesis testing, propose a geometry-aware sensor selection algorithm, and validate the approach using real testbed data.

Kaan Buyukkalayci, Osama Hanna, Christina Fragouli

Recent work shows that when contexts are drawn i.i.d., linear contextual bandits can be reduced to single-context linear bandits. This ``contexts are cheap" perspective is highly advantageous, as it allows for sharper finite-time analyses and leverages mature techniques from the linear bandit literature, such as those for misspecification and adversarial corruption. Motivated by applications with temporally correlated availability, we extend this perspective to Markovian contextual linear bandits, where the action set evolves via an exogenous Markov chain. Our main contribution is a reduction that applies under uniform geometric ergodicity. We construct a stationary surrogate action set to solve the problem using a standard linear bandit oracle, employing a delayed-update scheme to control the bias induced by the nonstationary conditional context distributions. We further provide a phased algorithm for unknown transition distributions that learns the surrogate mapping online. In both settings, we obtain a high-probability worst-case regret bound matching that of the underlying linear bandit oracle, with only lower-order dependence on the mixing time.