Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations
研究了多秘书问题中当秘书估值分布连续或未知时遗憾随职位数对数增长，并将结论推广到更一般的在线线性规划，改进了现有上界并给出了下界。
In 2019, Alessandro Arlotto and Itai Gurvich proved that the expected regret in the multisecretary problem is uniformly bounded as the number of jobs to fill goes to infinity. However, they modeled the secretary valuation distribution as discrete and known, and they concluded their article by explaining that they did not know whether their bound would hold with continuous or unknown valuation distributions. In “Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations,” Robert L. Bray provides an answer, furnishing lower and upper bounds that demonstrate that the regret in multisecretary problem grows like the logarithm of the number of positions to fill when the distribution of secretary valuations continuous or unknown. He then develops the argument to establish analogous bounds for the more general online linear program, defined by Xiaocheng Li and Yinyu Ye. Bray tightens Li and Ye’s upper regret bound and develops a corresponding lower regret bound. To create these bounds, Bray develops several new convergence results for the online linear program’s dual variables.