Abstract
We study a "pen testing" problem, in which we are given n pens with unknown amounts of ink X₁, X₂, …, X_n, and we want to choose a pen with the maximum amount of remaining ink in it. The challenge is that we cannot access each X_i directly; we only get to write with the ith pen until either a certain amount of ink is used, or the pen runs out of ink. In both cases, this testing reduces the remaining ink in the pen and thus the utility of selecting it.
Despite this significant lack of information, we show that it is possible to approximately maximize our utility up to an O(log n) factor. Formally, we consider two different setups: the "prophet" setting, in which each X_i is independently drawn from some distribution ?_i, and the "secretary" setting, in which (X_i)_{i=1}^n is a random permutation of arbitrary a₁, a₂, …, a_n. We derive the optimal competitive ratios in both settings up to constant factors. Our algorithms are surprisingly robust: (1) In the prophet setting, we only require one sample from each ?_i, rather than a full description of the distribution; (2) In the secretary setting, the algorithm also succeeds under an arbitrary permutation, if an estimate of the maximum a_i is given.
Our techniques include a nontrivial online sampling scheme from a sequence with an unknown length, as well as the construction of a hard, nonuniform distribution over permutations. Both might be of independent interest. We also highlight some immediate open problems and discuss several directions for future research.
BibTeX  Entry
@InProceedings{qiao_et_al:LIPIcs.ITCS.2023.91,
author = {Qiao, Mingda and Valiant, Gregory},
title = {{Online Pen Testing}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {91:191:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772631},
ISSN = {18688969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17594},
URN = {urn:nbn:de:0030drops175940},
doi = {10.4230/LIPIcs.ITCS.2023.91},
annote = {Keywords: Optimal stopping, online algorithm}
}
Keywords: 

Optimal stopping, online algorithm 
Collection: 

14th Innovations in Theoretical Computer Science Conference (ITCS 2023) 
Issue Date: 

2023 
Date of publication: 

01.02.2023 