When Adaptivity Counts: Hit-Count Inspection with Information-Only Queries

Abstract

We study a hidden-set problem in which perfect point queries acquire information but earn no reward, while a separate exact-q terminal action earns its hit count. Every instance satisfies V_ad^# <= q V_batch^#; taking the supremum over all depths and finite positive-batch instances at fixed q gives q. For q >= 2 and I >= 1, a staircase has ratio at least q/(1+2q/I) and approaches q as depth and ground size grow. The worst-case additive gap tends to q-1; at depth two, a four-state prior attains the sharp gap q(q-1)/[2(2q-1)]. Under one-hit reward, adaptivity instead collapses: a prior-free pointwise compilation makes all policy classes equal weighted maximum (I+q)-coverage. For hit count, the batch objective is not generally submodular, while a coverage proxy gives a (1-1/e)/q approximation. By contrast, reward-bearing active search admits ratios that grow with feedback-batch size. A two-round q=1 witness exhibits one mechanism by which public reward feedback restores adaptivity in multiday social deduction. Lean checks the finite identities and constructions listed in the verification ledger.