Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality

We thank the reviewer for the valuable feedback. Below we address your concerns.

W1 and Q1: This paper mentions that the use in analysis is substantially different from that of Guo et al. (2019), but not in detail. As for me, the idea of using Bernstein inequality to construct stochastically dominated empirical distributions is similar. Could the authors explain in detail how their use of Bernstein inequality is different from Guo et al. (2019)?

A: Our use differs significantly in both the algorithmic perspective and the analysis.

• Algorithmic perspective. Since Guo et al. (2019) focuses on the sample complexity, they first collect sufficient samples over all the distributions of the boxes to construct empirical distributions, and then output a near-optimal policy from pessimistic distributions, which reallocate the probability mass of empirical distributions toward lower outcomes. This is exactly the opposite of our optimistic scheme, where we shift mass to higher outcomes. As we focus on the regret minimization, the algorithm needs to balance exploration and exploitation. To this end, our algorithm uses optimistic distributions with Bernstein-type adjustment, which encourages the algorithm to adaptively explore the distributions of the boxes.

• Analytical perspective. The analysis of (Guo et al. 2019) requires sufficient and equal amount of samples for each box. However, since our algorithm adaptively explores boxes, the sample size varies across boxes, and some boxes may only have a small sample size. We therefore conduct a finer‑grained study of the exploration process and show that a Bernstein‑type concentration bound naturally captures its adaptiveness and delivers the desired regret guarantees.

W2 and Q2: it is interesting and also natural to ask why the dependence on the number of boxes $n$ is different for the non-contextual and contextual problems in this paper, but the authors do not discuss this point. Could the authors address why the similar algorithm gives different reliance on $n$ for the regret bound on the non-contextual and contextual problems?

A: The different dependence on $n$ arises primarily because in the contextual setting, our analysis needs to bound the estimation error of context-dependent mean, which leads to a linear dependence on $n$. Unlike the non-contextual case where the reward samples are i.i.d., in the contextual case the mean reward varies with the context, and the observed samples are not identically distributed across rounds. To ensure stochastic dominance, we construct an optimistic distribution by shifting the sample values in an optimistic manner. The regret introduced by this value-shifting scales linearly with $n$, and the technique that yields the $\widetilde{O}(\sqrt{nT})$ bound in the non-contextual setting, does not extend to the contextual case.

We thank the reviewer for the valuable and positive feedback. Below we address your concerns.

W1: The boundedness assumption on the random noise in the linear contextual case seems to be a limiting assumption. In the traditional linear bandits, it suffices to assume a bounded mean reward, while the noise can have an unbounded supported as long as it is sub-Guassian.

A: In fact, this assumption can be relaxed. For each box, if the noise distribution is sub-Gaussian, then, the reward distribution is also sub-Gaussian, and our algorithms still work with minor modifications. Specifically, if the reward distribution of box $i$ is $K_i$-sub-Gaussian, one can set a range $[-K_i \sqrt{2\log(2T^2n)},K_i\sqrt{2\log(2T^2n)}]$. Then, the algorithm updates parameters only if the received reward of each box $i$ is within range of $[-K_i \sqrt{2\log(2T^2n)},K_i\sqrt{2\log(2T^2n)}]$. On those rounds, the algorithm and its regret analysis coincide exactly with the bounded‑reward setting. Meanwhile, by a union bound on sub-Gaussian tails, the probability that any reward ever exceeds its range is at most $1/T$. Therefore, its contribution to the expected regret is only $\widetilde{O}(1)$.

W2: Does $\Omega(\sqrt{nT})$ lower bound in Gatmiry et al. [16] apply here?

A: The $\Omega(\sqrt{nT})$ lower bound in Gatmiry et al. [16] indeed applies to our setting since their lower bound holds even in the full-information setting, thereby applying to ours. Specifically, Gatmiry et al., prove $\Omega(\sqrt{nT})$ regret lower bound by using $\Omega(n/\epsilon^2)$ lower bound for sample complexity. To see this, we here reiterate their proof idea. For the full-information feedback, if an online algorithm achieves $o(\sqrt{nT})$ regret, then one can use online-to-batch conversion to get a $\epsilon$-optimal policy with $o(n/\epsilon^2)$ sample complexity, which contradicts to $\Omega(n/\epsilon^2)$ lower bound.

Q1: Can I check that if I apply the algorithm in Section 4 on the non-contextual case (1 feature dimension per box), do we end up with $O(n^2\sqrt{T})$ regret bound?

A: Our contextual setting uses a separate parameter $\theta_i$ for each box $i$, which subsumes the non-contextual case as a special instance. In the non-contextual case, it suffices to set the feature dimension $d=1$, leading to a $\widetilde{O}(n\sqrt{T})$ regret bound. While this is worse than the $\widetilde{O}(\sqrt{nT})$ bound of our dedicated non-contextual algorithm, the linear dependence on $n$ arises from the estimation error of context-dependent means. The technique used to obtain the tighter $\widetilde{O}(\sqrt{nT})$ bound does not carry over to the contextual setting. Whether the $\widetilde{O}(nd\sqrt{T})$ bound is tight remains an open question for future work.

Q2: The authors' model could have some connection to the cascading bandit model: ``Kveton et al., Cascading Bandits: Learning to Rank in the Cascade Model, ICML 2015''. While the two models involve semi-bandit feedback depending on the ordering of basic arms/boxes, they are quite different in terms of the reward function. Nevertheless, I believe the above work is worth mentioning.

A: We thank the reviewer for highlighting this interesting paper. We will make sure to include this reference in the revision.

We thank the reviewer for positive feedback and your acknowledgment on our contributions. Below we address your concerns.

Q1: Is it possible to establish $\widetilde{O}(\sqrt{nT})$ regret bound with high probability?

A: Yes. We can obtain a high-probability bound of $\widetilde{O}(\sqrt{nT})$ under regret metric $\sum_{t=1}^T (R(\sigma\_{D};D)-R(\sigma\_{t};D))$ via two modifications in our analysis. First, LHS of Eq(4) now has no expectation, but since $\sigma_t$ and $H_{t,i}$ are deterministic given history, we have $R(\sigma\_t;H\_{t,i-1})-R(\sigma\_t;H\_{t,i}) = \mathbb{E}\_t [R(\sigma_t;H_{t,i-1})-R(\sigma_t;H_{t,i})]$ where $\mathbb{E}\_t[\cdot]$ is the conditional expectation given history before round $t$. Then, we can follow the same analysis to arrive at $\sqrt{\sum_{i,t} \frac{Q_{t,i}}{m_{t,i}} }$. To handle this, let $M_{t,i}=\frac{Q_{t,i}-I_{t,i}}{m_{t,i}}$, and $\\{M_{t,i}\\}\_{t}$ is martingale difference sequence. By Freedman's inequality, with probability at least $1-\delta$, we have $\sum_{t} M_{t,i} \leq \sqrt{2V \log(1/\delta)} + \log(1/\delta)$ where $V= \sum_{t=1}^T \mathbb{E}\_t [M_{t,i}^2 ]$. Notice that $V =\frac{ Q_{t,i} -Q_{t,i}^2 }{m_{t,i}} \leq \frac{ Q_{t,i} }{m_{t,i}}$. Thus, we have $\sum_{t} M_{t,i} \leq \sqrt{ 2\log(1/\delta)\sum_{t}Q_{t,i}/m_{t,i} }+\log(1/\delta) \leq \frac{1}{2}\sum_{t}Q_{t,i}/m_{t,i}+ 2\log(1/\delta)$ where the last step uses the AM-GM inequality. Rearranging it gives $\sum_{t=1}^T \frac{Q_{t,i}}{m_{t,i}} \leq O (\log(1/\delta)+\sum_{t=1}^T \frac{I_{t,i}}{m_{t,i}} )$. Therefore, by choosing $\delta$ properly and applying a union bound, with high probability, the regret is bounded by $\widetilde{O}(\sqrt{nT})$.

Q2: The authors assume that the reward distributions have a bounded support. Can the results be extended to distributions with unbounded support?

A: For an arbitrary unbounded distribution, we believe the online Pandora's Box is intractable without further assumption. The main hardness here is that a box may yield an extremely large reward with a very small probability. For example, consider two instances in which there is only one box cost $1$. In instance $I_1$, the box generates reward $2^T$ with probability $2^{-T+1}$, and generates reward $0$ otherwise. In the other instance $I_2$, the box generates the same reward with probability $2^{-T-1}$ and $0$ otherwise. Then, the learner needs to decide whether to open the box. The optimal strategy in $I_1$ always opens the box, whereas the optimal strategy in $I_2$ never opens it. However, distinguishing these two instances are statistically hard within $T$ rounds, and thus the online Pandora's Box with arbitrary unbounded distribution is intractable.

However, if the reward distribution of each box is subgaussian, then, our algorithms still work with minor modifications. Specifically, if the reward distribution of box $i$ is $K_i$-subgaussian, one can set a range $[-K_i \sqrt{2\log(2T^2n)},K_i\sqrt{2\log(2T^2n)}]$. Then, the algorithm updates parameters only if the received reward of each box $i$ is within range of $[-K_i \sqrt{2\log(2T^2n)},K_i\sqrt{2\log(2T^2n)}]$. On those rounds, the algorithm and its regret analysis coincide exactly with the bounded‑reward setting. Meanwhile, by a union bound on subgaussian tails, the probability that any reward ever exceeds its range is at most $1/T$. Therefore, its contribution to the expected regret is only $\widetilde{O}(1)$.

Q3: For completeness, it is better to briefly reproduce the arguments from [2] leading to Eqn (4).

A: Thank you for the suggestion. We will reproduce those arguments in the next version.

We thank the reviewer for the valuable feedback. Below we address your concerns.

W1: Improvement of clarity and structure.

A: Thank you for the suggestions; we will edit the paper accordingly. In particular, we will better emphasize the intuition for the proofs in the main text and defer technical details to the appendix. That said, several of your comments are very minor and can be easily addressed. In fact, it is worth noting that all other reviewers commented and agreed that the paper is well-written. While we appreciate your suggestions and will revise accordingly, we sincerely hope that you could consider raising the score given that the main weakness you pointed out pertains to clarity and structure.

W2: Algorithm 1 is essentially Weitzman’s original policy for the classic setting, but this is never explicitly stated.

A: Algorithm 1 is a general version of Weitzman's algorithm since it accepts any threshold vector as an input. Algorithm 1 coincides with the classical Weitzman algorithm precisely when those thresholds are chosen optimally for the true underlying distributions, as noted in Section 2.

Q1: Why the contextual-linear setting is defined on a $[-1/4,1/4]$ support?

A: This choice is made purely for simplicity, avoiding the need to re‑derive some standard results under a different scaling. In fact, both our algorithm and analysis easily extend to any other $[-K,K]$ support setting by simply replacing every $[-1/4,-1/4]$-bounded argument with its $[-K,K]$-bounded analogue. We will clarify this in the revision to make it clear that $[-1/4,1/4]$ is for convenience and to make the paper concise by citing existing work where possible.

Q2: Why the principle of optimism under uncertainty is helpful for improving the regret guarantee in this work?

A: Our contribution here does not stem from the optimism under uncertainty principle, which Agarwal et al. (2024) already apply yielding only a $\widetilde{O}(n\sqrt{T})$ regret bound. While we build on their framework, the improvement we obtain derives from taking different approach altogether wherein we construct the optimistic distribution (shift probability mass based on Bernstein type bound), and more importantly, the improvement owes to our highly refined analysis. We highlight these differences in algorithm design and analysis in Section 3.1 and Section 3.2, respectively.

Q3: What is the weak benchmark considered by Gergatsouli and Tzamos? Similarly, what is the optimal policy benchmark considered in Gatmiry et al.? What is the benchmark used in this work for both the non-contextual and contextual cases?

A: Since Gergatsouli and Tzamos (2022) allow the distributions of the boxes to be chosen adversarially across rounds, competing against the optimal strategy is intractable. Therefore to ensure sublinear regret, Gergatsouli and Tzamos (2022) introduce two weak benchmarks: (1) a non-adaptive benchmark that opens the same fixed set of boxes in every round, and (2) a partially-adaptive benchmark that may choose a different set in each round based on the algorithm’s past choices. On the other hand, Gatmiry et al., (2024) and our work (in both non-contextual and contextual settings) both use the optimal strategy as the benchmark. This is Weitzman's algorithm with full knowledge of the product distribution at each round. We will make clarification in the next version.