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

Read full text
Authors: Tamashiro, Takuya
Cited by: 72
References: 3

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^# = 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.

Fields of Study & Subjects

Machine Learning and Algorithms Optimization and Search Problems Advanced Bandit Algorithms Research

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
29 August 2026
Language
EN