Assume a set $S$ of elements $\{s_1,..,s_n\}$, each which has a hidden label 'active' or 'inactive'. Assume there are $m\ll n$ active elements in total. You are allowed to iteratively perform a single operation, which is to choose any subset $Q\subseteq S$ which returns $any(Q)$ or with other words if any of the chosen elements are active. The goal is to distinguish exactly which elements are active and which are inactive. The question is if there exists an optimal policy of how to solve this in a minimal number of expected operations, either for a fixed known $m$ or for a probability distribution $p(m)$.

My first approach was to try to solve this recursively, but there was just too many ifs and special cases. By splitting in 2 until you reach an active element, discarding inactive subsets you get an algorithm that runs in $\mathcal{O}(m~log~n)$, but it is unclear whether that is optimal.

I'm looking for ideas and references as much as solutions. It just feels like there should be work that has approached this kind of problem previously.

Assume a set $S$ of elements $\{s_1,\dots,s_n\}$, each which has a hidden label 'active' or 'inactive'. Assume there are $m\ll n$ active elements in total. You are allowed to iteratively perform a single operation, which is to choose any subset $Q\subseteq S$ which returns $\mathrm{any}(Q)$ or with other words if any of the chosen elements are active. The goal is to distinguish exactly which elements are active and which are inactive. The question is if there exists an optimal policy of how to solve this in a minimal number of expected operations, either for a fixed known $m$ or for a probability distribution $p(m)$.

My first approach was to try to solve this recursively, but there was just too many ifs and special cases. By splitting in 2 until you reach an active element, discarding inactive subsets you get an algorithm that runs in $O(m\log n)$, but it is unclear whether that is optimal.

I'm looking for ideas and references as much as solutions. It just feels like there should be work that has approached this kind of problem previously.

Assume a set $S$ of elements $\{s_1,..,s_n\}$, each which has a hidden label 'active' or 'inactive'. You are allowed a single operation, which is to choose any subset $Q\subseteq S$ which returns $any(Q)$ or with other words if any of the chosen elements are active. The question is if there exists an optimal policy of how to solve this in a minimal number of expected operations, either for a fixed $|Q|$ or for a probability distribution $p(|Q|)$.

My first approach was to try to solve this recursively, but there was just too many ifs and special cases. By splitting in 2 until you reach an active element, discarding inactive subsets you get an algorithm that runs in $\mathcal{O}(|Q|~log~n)$, but it is unclear whether that is optimal.

I'm looking for ideas and references as much as solutions. It just feels like there should be work that has approached this kind of problem previously.

Assume a set $S$ of elements $\{s_1,..,s_n\}$, each which has a hidden label 'active' or 'inactive'. Assume there are $m\ll n$ active elements in total. You are allowed to iteratively perform a single operation, which is to choose any subset $Q\subseteq S$ which returns $any(Q)$ or with other words if any of the chosen elements are active. The goal is to distinguish exactly which elements are active and which are inactive. The question is if there exists an optimal policy of how to solve this in a minimal number of expected operations, either for a fixed known $m$ or for a probability distribution $p(m)$.

My first approach was to try to solve this recursively, but there was just too many ifs and special cases. By splitting in 2 until you reach an active element, discarding inactive subsets you get an algorithm that runs in $\mathcal{O}(m~log~n)$, but it is unclear whether that is optimal.

I'm looking for ideas and references as much as solutions. It just feels like there should be work that has approached this kind of problem previously.