Pith. sign in

REVIEW 4 major objections 6 minor 54 references

Markovian Pandora's box

T0 review · 4 major / 6 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For forest precedence graphs, the Markovian Pandora's box problem has a polynomial-time fully adaptive optimal strategy.

desk verdict A natural new model with a clever contraction idea, but the central exact algorithm has a load-bearing indexing bug in its DP. read the letter →

arxiv 2502.00228 v1 pith:JE5T4A4D submitted 2025-01-31 cs.GT

Yuanyuan Yang , Ruimin Zhang , Jamie Morgenstern , Haifeng Xu This is my paper · ORCID
classification cs.GT MSC 90C40
keywords MarkovianPandora'sboxgeneralizedreservationvaluefullyadaptivestrategiesorderconstraintsforestprecedencegraphsstatictransitionsubgraphoptimizationsequentialdecisionmaking
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces Markovian Pandora's box, a costly-search model in which one directed acyclic graph simultaneously states which boxes must be opened before which others and how each box's reward depends, Markovianly, on the reward of its predecessor. It claims that when this graph is a forest, the fully adaptive optimum—the best strategy whose stopping time and next box to open may both depend on all rewards seen so far—can be computed exactly in polynomial time and space. That matters because the fully adaptive optimum is NP-hard to approximate on general DAGs, so the forest case is a rare exactly solvable class. The decision is governed by a generalized reservation value per box, and in a forest the optimal strategy is to follow the available branch with the highest current value after minimal subtrees are contracted into single boxes with random costs. Under static transition, where every edge in a component shares one transition matrix, the paper gives faster algorithms that truncate each line to a short prefix, near-optimal on lines and multi-lines and a $\frac{1}{2}$-approximation on forests.

What carries the argument

The machinery is the generalized reservation value (GRV), a per-box threshold defined as the smallest current maximum reward at which the expected utility of optimally continuing equals the utility of stopping. The paper computes it from a dynamic-programming table of continuation values $\phi(x,s,i)$, storing the expected future max reward minus cost for every possible current best reward $x$, predecessor reward $s$, and next-box index $i$. In the forest algorithm, the same table is reused after contracting the descendants of a branch vertex into an equivalent single box with random cost and reward, so every contraction step preserves the GRV rule. Under static transition, the table becomes index-free and is solved by fixed-point iteration, and Markov-chain mixing bounds justify truncating lines to their first few boxes.

What would settle it

Construct a two-box line in which the first box has positive probability of yielding a reward $y$ above the starting threshold $x$, and compare the continuation value returned by the table lookup $RFRM(x, s_y, i+1)$ in Algorithm 3 with the value computed by dynamic programming from the state $\max\{x,y\}$. Any instance where the two values imply different opening decisions settles whether the table index is a typo; if the table value is wrong, the polynomial-time optimality claim fails.

Watch

Extended reading notes

Core claim

The central claim is that a threshold rule based on a generalized reservation value is exactly optimal for the fully adaptive Markovian Pandora's box on forests. For each box and each observed predecessor state, the generalized reservation value is the current best reward $x$ at which the decision maker is indifferent between stopping and paying the cost to open that box with optimal continuation; if the threshold exceeds $x$ the strategy proceeds, otherwise it stops. In a single line this reduces the problem to an optimal stopping time, and the paper proves the threshold can be precomputed in a polynomial-size equivalent-reward table. For multiple lines the optimal strategy probes the line whose next available box has the highest current generalized reservation value, and this remains true even though the choice is now fully adaptive. For a forest, the paper contracts each minimal tree below its root into one box with a correlated random reward and cost, reducing the graph to a multi-line instance and preserving the payoff table and thresholds through every contraction; iterating gives the polynomial-time exact optimum of Theorem 1.1.

Load-bearing premise

The load-bearing premise is that the dynamic-programming table in Algorithm 3 correctly uses the old maximum reward $x$ as the state index after a newly opened box reveals a larger reward $y$; if the correct index is the updated maximum $\max\{x,y\}$, then the stopping thresholds computed from the table are wrong on every continuation state where $y$ exceeds $x$.

Editorial extensions

If this is right

  • If Theorem 1.1 is correct, every Markovian Pandora's box instance whose precedence and correlation graph is a forest can be solved exactly rather than approximated, in time polynomial in the number of boxes and reward values.
  • The exact forest algorithm gives a concrete benchmark for measuring approximation loss on the NP-hard general-DAG problem, since any DAG algorithm can be compared against its optimal forest sub-instances.
  • Under static transition, near-optimal play on a line needs only a bounded mixing-time prefix, so exploration cost stays controlled as the graph grows; the speedup over the exact algorithm grows with graph size.
  • For forest-structured static-transition instances, restricting attention to the best directed line already guarantees half the expected payoff of any adaptive strategy, up to an additive $\delta$.
  • The adaptivity-gap result means fully adaptive strategies strictly beat partially adaptive ones in this model, so the paper's focus on fully adaptive optimality addresses a real loss in simpler strategy classes.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Inference: The GRV-based contraction may extend to graphs of bounded treewidth, since forest contraction is a special case of repeatedly eliminating branch vertices; the paper does not claim this.
  • Inference: The static-transition truncation result suggests an online or learning version of the problem where transition matrices are estimated from data could keep regret bounded by mixing time; the paper does not study learning.
  • Inference: A natural testable extension is to replace the single best-line search in the forest approximation by a search over a constant number of lines, which might improve the $\frac{1}{2}$ constant while keeping the polylogarithmic runtime.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

Summary. The paper introduces the Markovian Pandora's Box problem, where boxes have known probing costs and Markovianly correlated rewards governed by the same directed acyclic graph that encodes precedence constraints. It proposes a generalized reservation value (GRV) and claims an exact polynomial-time fully adaptive algorithm for forest-structured precedence graphs (Theorem 1.1), building from a single-line dynamic program (Algorithm 3), then extending to multi-line settings and forests via contraction. It also gives faster near-optimal and 1/2-approximation algorithms under a static-transition assumption. The central claims are that the GRV rule is optimal and that all components can be computed in polynomial time and space.

Significance. If the central claims held, the paper would be a significant contribution: it would identify a structured correlation setting in which the fully adaptive optimum is exactly computable in polynomial time, contrasting with the NP-hardness of the general DAG case, and it would introduce a natural new model connecting Markovian reward dependencies with precedence constraints. The paper also proposes concrete approximation algorithms under static transitions. However, the manuscript as written does not establish these claims: the main dynamic programming recurrence contains a load-bearing indexing error, and several supporting lemmas are asserted with inadequate or flawed proof. The contribution therefore currently remains at the level of a promising framework rather than a verified set of results.

major comments (4)
  1. [Appendix C.2, Algorithm 3, lines 16 and 22] The recurrence in Algorithm 3 uses the pre-opening maximum x to index the continuation tables after observing reward y, but the actual next state has current maximum max{x,y}. Specifically, line 16 evaluates max{x, y, RFRM(x, s_y, i+1)} and line 22 builds RFRM(x,s,i) as max{y, RFRM(x, s_y, i+1)}, always with first argument x. This contradicts the Bellman equation in Section 3.2, which requires the continuation value Φ^{τ*}(max{x,s_i}, s_i, i+1), and Definition 3.2, whose stopping rule depends on the updated threshold. When y > x, the table applies stopping decisions appropriate for the lower threshold x, so the computed entries are not the Bellman values of the stated problem. Since every GRV lookup and every forest contraction uses this table, Theorems 3.7, 4.5, E.5, and 1.1 are unsupported as written.
  2. [Sections 3.2 and 3.3, Definition 3.3 and Theorem 3.5] The generalized reservation value is defined in terms of the optimal stopping time τ*, and Theorem 3.5 then asserts that comparing the current maximum to the GRV recovers an optimal strategy. The only independent validation of this characterization is the dynamic programming table that computes Φ and the GRV. Because Algorithm 3 does not in fact compute the Bellman value (see previous comment), the non-circularity of the GRV definition is not established. The argument needs a correct DP table or an alternative fixed-point characterization before the optimality claim can be accepted.
  3. [Appendix D.2, Lemma D.4 and Theorem 4.4] The proof of Lemma D.4, which is the key exchange argument underlying multi-line optimality, relies on the assertion that E[A|A ≥ X] > X; this inequality is not true in general when equality can hold with positive probability. The proof also uses the notation π_A, λ_A, ρ_A (and their B counterparts) as both events and probabilities without a formal definition, and the displayed table-based calculation contains multiple ambiguous terms. Since Theorem 4.4 (the multi-line GRV optimality theorem) and the forest contraction argument depend on this lemma, the exact optimality proof is incomplete even setting aside the Algorithm 3 issue.
  4. [Section 6.3, Lemma 6.9] Lemma 6.9 asserts a 1/2 adaptivity gap for forest-structured Markovian precedence graphs, citing BFLL20 and stating that the proof 'generalizes easily' from the independent-box setting. No proof is provided, and the generalization to Markovian correlations is not immediate because the forest structure interacts with the reward dependencies. This lemma is load-bearing for Theorem 6.10 (the 1/2 approximation for forests under static transition); the claim needs a complete proof or a precise citation of a result that covers this setting.
minor comments (6)
  1. [Throughout] The manuscript contains numerous typos and duplicated words (for example, 'irreducible, irreducible' in Theorem F.15 and 'in put' in Theorem F.13). The paper would benefit from a careful proofreading pass.
  2. [Algorithm 1, line 8] The variable j is initialized to 1 and never updated, yet the algorithm returns 'box bj that is opened and with the max reward.' This should either be updated during the loop or the return statement should be clarified.
  3. [Definition 5.1] A directed tree is defined as a connected DAG where removing any edge disconnects the graph, and a directed forest as a DAG whose components are trees. Standard arborescence terminology would be clearer, and the definition should specify whether edges are directed away from roots or in some other orientation.
  4. [Section 4, Theorem 4.5 proof] The proof begins by analyzing space, then says 'Next, we analyze the space complexity' before discussing runtime. The second paragraph appears to conflate runtime and space; it should be reorganized into separate time and space complexity arguments.
  5. [Algorithm 2, line 1] The variable t is set to 1 but never used, and the loop condition references 'minimal trees in graph G0' while the graph is named bG. These inconsistencies should be fixed.
  6. [Theorem 1.2] The displayed equation for the forest case has unbalanced brackets and the expression E[max_{i∈G} R_i − Σ_{i∈G} c_i] is not well-formed. The statement should be rewritten with precise notation.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation is a Bellman-type DP plus compositional contraction; the flagged stale-max issue is a correctness concern, not a circular reduction.

full rationale

I walked the claimed derivation chain: the GRV (Def. 3.3) is defined through the optimal continuation value Phi, and the optimality theorem (Thm. 3.5) is a threshold characterization proved from Lipschitzness and monotonicity of Phi (Lem. C.1, C.3), not a restatement of the definition. Algorithm 3 is a backward dynamic program over states; it does not fit any parameter to a target quantity and then rename it as a prediction. The equivalent-box constructions (Lem. 4.2, D.1, D.3) are coupling/representation arguments, not imported conclusions. The forest contraction (Alg. 2, Thm. E.5) composes the independently argued multi-line solution, and the 1/2-approximation result imports its adaptivity gap from [BFLL20], whose authors do not overlap with this paper; the cited NP-hardness for general DAGs is from [CGMT21], also non-overlapping. The only substantive concern I found is a potential correctness flaw in Appendix C.2, Algorithm 3 line 16: after opening box i and observing y, the continuation is looked up as RFRM(x, s_y, i+1) and cFR(x, s_y, i+1), using the old maximum x rather than max{x,y}. If this is indeed the intended recurrence, the DP does not compute the Bellman value, so Lemma 3.6, Theorem 3.7, and the forest results built on them would be unproven. But that is an incorrect recurrence, not a circular one: no equation is made equal to its input by construction, and no fitted value is renamed as a prediction. Correctness failure and circularity are distinct; under the hard rule requiring a quoted reduction, I find no circular step.

Assumptions & free parameters 0 free parameters · 6 assumptions · 1 invented entities

The central claim rests on the correctness of the GRV dynamic program, the implicit independence of separate tree components, the validity of contraction of subtrees into equivalent random-cost boxes, and, for the static-transition results, the generalization of the BFLL20 adaptivity gap to Markovian forests. The first of these is undercut by an apparent indexing error in Algorithm 3; the last is asserted without proof.

assumptions (6)
  • domain assumption Finite reward support and shared value set V for all boxes.
    Section 2.1 assumes WLOG that all rewards share the same finite value set to make the DP table finite.
  • domain assumption Static transition: same transition matrix for all edges in a component (Assumption 6.1).
    Used for all faster algorithms; the definition of component is problematic, making the assumption ill-defined for a DAG.
  • domain assumption Irreducibility and aperiodicity of the transition matrix (Assumption 6.3).
    Needed for convergence to a stationary distribution and the mixing-time bounds used in the near-optimal prefix theorems.
  • ad hoc to paper The adaptivity gap lemma of BFLL20 generalizes to Markovian forests (Lemma 6.9).
    The proof is not given; the text says the original proof generalizes easily, which is load-bearing for the 1/2 forest approximation.
  • domain assumption Boxes in different components of the forest are independent.
    Not explicitly stated; the multi-line and forest algorithms assume rewards in different lines are independent so that a line's GRV depends only on its own history.
  • standard math Standard Markov chain convergence and mixing time bounds (Lemma F.8, from LP17).
    Imported standard theorem; used to prove Lemmas 6.5 and F.14.
invented entities (1)
  • Equivalent single box with random cost (Def. 4.1)
    purpose: Contract a hyperbox or a subtree into a single box with correlated random reward and cost so that the multi-line or forest problem reduces to probing a small set of boxes.
    The equivalence is asserted via a coupling construction (Lem. D.1) that depends on the optimal stopping time for the subtree; its correctness is exactly what the forest contraction needs, and the paper does not provide a proof that the contraction preserves the optimal value, only a brief assertion in Thm. E.5.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Markovian Pandora's box." pith.science (2026). https://pith.science/paper/JE5T4A4D

@misc{pith2026250200228,
  author       = {Pith},
  title        = {Pith review of: Markovian Pandora's box},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JE5T4A4D}},
  note         = {Machine review of arXiv:2502.00228}
}
read the original abstract

In this paper, we study the Markovian Pandora's Box Problem, where decisions are governed by both order constraints and Markovianly correlated rewards, structured within a shared directed acyclic graph. To the best of our knowledge, previous work has not incorporated Markovian dependencies in this setting. This framework is particularly relevant to applications such as data or computation driven algorithm design, where exploration of future models incurs cost. We present optimal fully adaptive strategies where the associated graph forms a forest. Under static transition, we introduce a strategy that achieves a near optimal expected payoff in multi line graphs and a 1/2 approximation in forest-structured graphs. Notably, this algorithm provides a significant speedup over the exact solution, with the improvement becoming more pronounced as the graph size increases. Our findings deepen the understanding of sequential exploration under Markovian correlations in graph-based decision-making.

Figures

Figures reproduced from arXiv: 2502.00228 by the authors.

Figure 1
Figure 1. Reduction From Tree to Multi-Line Setting [PITH_FULL_IMAGE:figures/full_fig_p028_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

54 extracted references · 49 canonical work pages

  1. [1]

    Self-improving algorithms

    Nir Ailon, Bernard Chazelle, Kenneth L Clarkson, Ding Liu, Wolfgang Mulzer, and C Seshadhri. Self-improving algorithms. SIAM Journal on Computing , 40(2):350--375, 2011

    work page 2011

  2. [2]

    Pandora's box problem over time

    Georgios Amanatidis, Federico Fusco, Rebecca Reiffenh \"a user, and Artem Tsikiridis. Pandora's box problem over time. arXiv preprint arXiv:2407.15261 , 2024

    work page arXiv 2024

  3. [3]

    The pandora's box problem with sequential inspections

    Ali Aouad, Jingwei Ji, and Yaron Shaposhnik. The pandora's box problem with sequential inspections. Available at SSRN 3726167 , 2020

    work page 2020

  4. [4]

    Learning to prune: Speeding up repeated computations

    Daniel Alabi, Adam Tauman Kalai, Katrina Liggett, Cameron Musco, Christos Tzamos, and Ellen Vitercik. Learning to prune: Speeding up repeated computations. In Conference on Learning Theory , pages 30--33. PMLR, 2019

    work page 2019

  5. [5]

    Ordered consumer search

    Mark Armstrong. Ordered consumer search. Journal of the European Economic Association , 15(5):989--1024, 2017

    work page 2017

  6. [6]

    Submodular stochastic probing on matroids

    Marek Adamczyk, Maxim Sviridenko, and Justin Ward. Submodular stochastic probing on matroids. Mathematics of Operations Research , 41(3):1022--1038, 2016

    work page 2016

  7. [7]

    Random search for hyper-parameter optimization

    James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of machine learning research , 13(2), 2012

    work page 2012

  8. [8]

    The design and price of information

    Dirk Bergemann, Alessandro Bonatti, and Alex Smolin. The design and price of information. American economic review , 108(1):1--48, 2018

    work page 2018

Show all 54 references
  1. [9]

    Pandora’s problem with nonobligatory inspection: Optimal structure and a ptas

    Hedyeh Beyhaghi and Linda Cai. Pandora’s problem with nonobligatory inspection: Optimal structure and a ptas. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 803--816, 2023

    2023

  2. [10]

    Recent developments in pandora's box problem: Variants and applications

    Hedyeh Beyhaghi and Linda Cai. Recent developments in pandora's box problem: Variants and applications. ACM SIGecom Exchanges , 21(1):20--34, 2024

    2024

  3. [11]

    How much data is sufficient to learn high-performing algorithms? Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC) 2021 , 2019

    Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data is sufficient to learn high-performing algorithms? Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC) 2021 , 2019

    2021

  4. [12]

    Learning to branch

    Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In International conference on machine learning , pages 344--353. PMLR, 2018

    2018

  5. [13]

    Pandora’s problem with deadlines

    Ben Berger, Tomer Ezra, Michal Feldman, and Federico Fusco. Pandora’s problem with deadlines. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 38, pages 20337--20343, 2024

    2024

  6. [14]

    Pandora's box problem with order constraints

    Shant Boodaghians, Federico Fusco, Philip Lazos, and Stefano Leonardi. Pandora's box problem with order constraints. In Proceedings of the 21st ACM Conference on Economics and Computation , pages 439--458, 2020

    2020

  7. [15]

    Pandora's problem with nonobligatory inspection

    Hedyeh Beyhaghi and Robert Kleinberg. Pandora's problem with nonobligatory inspection. In Proceedings of the 2019 ACM Conference on Economics and Computation , pages 131--132, 2019

    2019

  8. [16]

    Learning-theoretic foundations of algorithm configuration for combinatorial partitioning problems

    Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. Learning-theoretic foundations of algorithm configuration for combinatorial partitioning problems. In Conference on Learning Theory , pages 213--274. PMLR, 2017

    2017

  9. [17]

    Combinatorial selection with costly information

    Shuchi Chawla, Dimitris Christou, Amit Harlev, and Ziv Scully. Combinatorial selection with costly information. arXiv preprint arXiv:2412.03860 , 2024

    2024 arXiv

  10. [18]

    Revenue maximization for query pricing

    Shuchi Chawla, Shaleen Deep, Paraschos Koutrisw, and Yifeng Teng. Revenue maximization for query pricing. Proceedings of the VLDB Endowment , 13(1):1--14, 2019

    2019

  11. [19]

    Query strategies for priced information

    Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon Kleinberg, Prabhakar Raghavan, and Amit Sahai. Query strategies for priced information. In Proceedings of the thirty-second annual ACM symposium on Theory of computing , pages 582--591, 2000

    2000

  12. [20]

    Approximating pandora's box with correlations

    Shuchi Chawla, Evangelia Gergatsouli, Jeremy McMahan, and Christos Tzamos. Approximating pandora's box with correlations. arXiv preprint arXiv:2108.12976 , 2021

    2021 arXiv

  13. [21]

    Pandora's box with correlations: Learning and approximation

    Shuchi Chawla, Evangelia Gergatsouli, Yifeng Teng, Christos Tzamos, and Ruimin Zhang. Pandora's box with correlations: Learning and approximation. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 1214--1225. IEEE, 2020

    2020

  14. [22]

    Sequential information maximization: When is greedy near-optimal? In Conference on Learning Theory , pages 338--363

    Yuxin Chen, S Hamed Hassani, Amin Karbasi, and Andreas Krause. Sequential information maximization: When is greedy near-optimal? In Conference on Learning Theory , pages 338--363. PMLR, 2015

    2015

  15. [23]

    Submodular surrogates for value of information

    Yuxin Chen, Shervin Javdani, Amin Karbasi, J Bagnell, Siddhartha Srinivasa, and Andreas Krause. Submodular surrogates for value of information. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 29, 2015

    2015

  16. [24]

    Self-improving algorithms for convex hulls

    Kenneth L Clarkson, Wolfgang Mulzer, and C Seshadhri. Self-improving algorithms for convex hulls. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1546--1565. SIAM, 2010

    2010

  17. [25]

    Competitive information design for pandora's box

    Bolin Ding, Yiding Feng, Chien-Ju Ho, Wei Tang, and Haifeng Xu. Competitive information design for pandora's box. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 353--381. SIAM, 2023

    2023

  18. [26]

    Product ranking on online platforms

    Mahsa Derakhshan, Negin Golrezaei, Vahideh Manshadi, and Vahab Mirrokni. Product ranking on online platforms. Management Science , 68(6):4024--4041, 2022

    2022

  19. [27]

    Whether or not to open pandora's box

    Laura Doval. Whether or not to open pandora's box. Journal of Economic Theory , 175:127--158, 2018

    2018

  20. [28]

    Pandora box problem with nonobligatory inspection: Hardness and approximation scheme

    Hu Fu, Jiawei Li, and Daogao Liu. Pandora box problem with nonobligatory inspection: Hardness and approximation scheme. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 789--802, 2023

    2023

  21. [29]

    Asking the right questions: Model-driven optimization using probes

    Ashish Goel, Sudipto Guha, and Kamesh Munagala. Asking the right questions: Model-driven optimization using probes. In Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , pages 203--212, 2006

    2006

  22. [30]

    The markovian price of information

    Anupam Gupta, Haotian Jiang, Ziv Scully, and Sahil Singla. The markovian price of information. In Integer Programming and Combinatorial Optimization: 20th International Conference, IPCO 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings 20 , pages 233--246. Springer, 2019

    2019

  23. [31]

    Sorting and selection with structured costs

    Anupam Gupta and Amit Kumar. Sorting and selection with structured costs. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science , pages 416--425. IEEE, 2001

    2001

  24. [32]

    Bandit algorithms for prophet inequality and pandora's box

    Khashayar Gatmiry, Thomas Kesselheim, Sahil Singla, and Yifan Wang. Bandit algorithms for prophet inequality and pandora's box. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 462--500. SIAM, 2024

    2024

  25. [33]

    A stochastic probing problem with applications

    Anupam Gupta and Viswanath Nagarajan. A stochastic probing problem with applications. In Integer Programming and Combinatorial Optimization: 16th International Conference, IPCO 2013, Valparaiso, Chile, March 18-20, 2013. Proceedings 16 , pages 205--216. Springer, 2013

    2013

  26. [34]

    Algorithms and adaptivity gaps for stochastic probing

    Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Algorithms and adaptivity gaps for stochastic probing. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms , pages 1731--1747. SIAM, 2016

    2016

  27. [35]

    Adaptivity gaps for stochastic probing: Submodular and xos functions

    Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Adaptivity gaps for stochastic probing: Submodular and xos functions. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1688--1702. SIAM, 2017

    2017

  28. [36]

    A pac approach to application-specific algorithm selection

    Rishi Gupta and Tim Roughgarden. A pac approach to application-specific algorithm selection. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science , pages 123--134, 2016

    2016

  29. [37]

    Online learning for min sum set cover and pandora’s box

    Evangelia Gergatsouli and Christos Tzamos. Online learning for min sum set cover and pandora’s box. In International Conference on Machine Learning , pages 7382--7403. PMLR, 2022

    2022

  30. [38]

    Weitzman's rule for pandora's box with correlations

    Evangelia Gergatsouli and Christos Tzamos. Weitzman's rule for pandora's box with correlations. arXiv preprint arXiv:2301.13534 , 2023

    2023 arXiv

  31. [39]

    Hyperparameter optimization: a spectral approach

    Elad Hazan, Adam Klivans, and Yang Yuan. Hyperparameter optimization: a spectral approach. In International Conference on Learning Representations , 2018

    2018

  32. [40]

    Non-stochastic best arm identification and hyperparameter optimization

    Kevin Jamieson and Ameet Talwalkar. Non-stochastic best arm identification and hyperparameter optimization. In Artificial intelligence and statistics , pages 240--248. PMLR, 2016

    2016

  33. [41]

    Delegated search approximates efficient search

    Jon Kleinberg and Robert Kleinberg. Delegated search approximates efficient search. In Proceedings of the 2018 ACM Conference on Economics and Computation , pages 287--302, 2018

    2018

  34. [42]

    Efficiency through procrastination: Approximately optimal algorithm configuration with runtime guarantees

    Robert Kleinberg, Kevin Leyton-Brown, and Brendan Lucier. Efficiency through procrastination: Approximately optimal algorithm configuration with runtime guarantees. In IJCAI , volume 3, page 1, 2017

    2017

  35. [43]

    Auto-weka: Automatic model selection and hyperparameter optimization in weka

    Lars Kotthoff, Chris Thornton, Holger H Hoos, Frank Hutter, and Kevin Leyton-Brown. Auto-weka: Automatic model selection and hyperparameter optimization in weka. Automated machine learning: methods, systems, challenges , pages 81--95, 2019

    2019

  36. [44]

    Descending price optimally coordinates search

    Robert Kleinberg, Bo Waggoner, and E Glen Weyl. Descending price optimally coordinates search. In Proceedings of the 2016 ACM Conference on Economics and Computation , pages 23--24, 2016

    2016

  37. [45]

    Hyperband: A novel bandit-based approach to hyperparameter optimization

    Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. The Journal of Machine Learning Research , 18(1):6765--6816, 2017

    2017

  38. [46]

    Multi-token markov game with switching costs

    Jian Li and Daogao Liu. Multi-token markov game with switching costs. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1780--1807. SIAM, 2022

    2022

  39. [47]

    Markov chains and mixing times , volume 107

    David A Levin and Yuval Peres. Markov chains and mixing times , volume 107. American Mathematical Soc., 2017

    2017

  40. [48]

    Discriminatory information disclosure

    Hao Li and Xianwen Shi. Discriminatory information disclosure. American Economic Review , 107(11):3363--3385, 2017

    2017

  41. [49]

    A more general pandora rule? Journal of Economic Theory , 160:429--437, 2015

    Wojciech Olszewski and Richard Weber. A more general pandora rule? Journal of Economic Theory , 160:429--437, 2015

    2015

  42. [50]

    The price of information in combinatorial optimization

    Sahil Singla. The price of information in combinatorial optimization. In Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms , pages 2523--2532. SIAM, 2018

    2018

  43. [51]

    Practical bayesian optimization of machine learning algorithms

    Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. Advances in neural information processing systems , 25, 2012

    2012

  44. [52]

    Optimizer benchmarking needs to account for hyperparameter tuning

    Prabhu Teja Sivaprasad, Florian Mai, Thijs Vogels, Martin Jaggi, and Fran c ois Fleuret. Optimizer benchmarking needs to account for hyperparameter tuning. In International conference on machine learning , pages 9036--9045. PMLR, 2020

    2020

  45. [53]

    Optimal search for the best alternative

    Martin L Weitzman. Optimal search for the best alternative. Econometrica: Journal of the Econometric Society , pages 641--654, 1979

    1979

  46. [54]

    Leapsandbounds: A method for approximately optimal algorithm configuration

    Gell \'e rt Weisz, Andras Gyorgy, and Csaba Szepesv \'a ri. Leapsandbounds: A method for approximately optimal algorithm configuration. In International Conference on Machine Learning , pages 5257--5265. PMLR, 2018

    2018

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.