Contextual Pandora’s Box
Authors: Alexia Atsidakou, Constantine Caramanis, Evangelia Gergatsouli, Orestis Papadigenopoulos, Christos Tzamos
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main result is a no-regret algorithm that performs comparably well against the optimal algorithm which knows all prior distributions exactly. Our main technical result shows that even when the sequence of contexts and distributions is adversarial, we can find a search strategy with sublinear average regret (compared to an optimal one) as long as no-regret algorithms exist for a much simpler online regression problem with a linear-quadratic loss functions. Theorem 3.1. Given an oracle that achieves expected regret r(T) after T rounds for Linear-Quadratic Online Regression, there is an algorithm that obtains O( p Tr(T)) regret for the CONTEXTUAL PANDORA S BOX problem. In addition to applying our framework to different stochastic optimization problems, an interesting future direction would be the empirical evaluation of our methods on real data. |
| Researcher Affiliation | Academia | Alexia Atsidakou1*, Constantine Caramanis1, Evangelia Gergatsouli2*, Orestis Papadigenopoulos3*, Christos Tzamos2,4 1University of Texas Austin, 2University of Wisconsin Madison, 3 Columbia University, 4 University of Athens |
| Pseudocode | Yes | Algorithm 1: Weitzman s algorithm. Algorithm 2: CPB: Contextual Pandora s Box Algorithm 3: Costly Feedback oracle from Full Information |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code or providing a link to a code repository for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not mention using or providing access information for any specific public datasets for training, validation, or testing. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical evaluation with data. Therefore, it does not provide specific dataset split information for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention specific ancillary software details with version numbers required to replicate an experiment. |
| Experiment Setup | No | The paper is theoretical and does not contain specific experimental setup details such as concrete hyperparameter values or training configurations. |