Worst number of questions needed to learn a monotonic predicate over a poset Consider $(X, \leq)$ a finite poset over $n$ items, and $P$ an unknown monotonic predicate over $X$ (i.e., for any $x$, $y \in X$, if $P(x)$ and $x \leq y$ then $P(y)$). I can evaluate $P$ by providing one node $x \in X$ and finding out if $P(x)$ holds or not. My goal is to determine exactly the set of nodes $x \in X$ such that $P(x)$ holds, using as few evaluations of $P$ as possible. (I can choose my queries depending on the answer of all previous queries, I am not required to plan all queries in advance.)

A strategy $S$ over $(X, \leq)$ is a function which tells me, as a function of the queries that I ran so far and their answers, which node to query, and which ensures that on any predicate $P$, by following the strategy, I will reach a state in which I know the value of $P$ on all nodes. The running time $r(S, P)$ of $S$ on a predicate $P$ is the number of queries required to know the value of $P$ on all nodes. The worst running time of $S$ is $wr(S) = \max_P r(S, P)$. An optimal strategy $S'$ is such that $wr(S') = \min_S wr(S)$.

My question is the following: given as input the poset $(X, \leq)$, how can I determine the worst running time of the optimal strategies?

[It is clear that for an empty poset $n$ queries will be needed (we need to ask about each single node), and that for a total order around $\lceil \log_2 n \rceil$ queries will be needed (doing a binary search to find the frontier). A more general result is the following information-theoretic lower bound: the number of possible choices for the predicate $P$ is the number $N_X$ of antichains of $(X, \leq)$ (because there is a one-to-one mapping between monotonic predicates and antichains interpreted as the maximal elements of $P$), so, since each query gives us one bit of information, we will need at least $\lceil \log_2 N_X \rceil$ queries, subsuming the two previous cases. Is this bound tight, or are them some posets whose structure is such that learning can require asymptotically more queries than the number of antichains?]
This is not a complete answer, but it's too long to be a comment.

I think I found an example for which the bound $\lceil \log_2 N_X \rceil$ is not tight.

Consider the following poset.  The ground set is $X=\{a_1, a_2, b_1, b_2\}$, and $a_i$ is smaller than $b_j$ for all $i,j\in\{1,2\}$. The other pairs are incomparable.  (The Hasse diagram is a $4$-cycle).

Let me identify the monotone properties with the upsets of the poset.  This poset has seven upsets: $\emptyset$, $\{b_1\}$, $\{b_2\}$, $\{b_1,b_2\}$, $\{a_1,b_1,b_2\}$, $\{a_2,b_1,b_2\}$, $\{a_1,a_2,b_1,b_2\}$, and this poset has seven antichains since the antichains are in one-to-one correspondence with the upsets.  So, $\lceil \log_2 N_X \rceil=\lceil \log_2 7 \rceil = 3$ for this poset.

Now, by adversary argument I'll show that any strategy needs at least four queries (so needs to query all elements).  Let's fix an arbitrary strategy.

If the strategy first queries $a_1$, then the adversary answers "$P(a_1)$ doesn't hold."  Then, we are left with five possibilities: $\emptyset$, $\{b_1\}$, $\{b_2\}$, $\{b_1,b_2\}$, $\{a_2,b_1,b_2\}$.  Thus, to determine which is the case, we need at least $\lceil \log_2 5\rceil = 3$ more queries.  In total, we need four queries.  The same argument applies if the first query is $a_2$.

If the strategy first queries $b_1$, then the adversary answers "$P(b_1)$ holds."  Then, we are left with five possibilities: $\{b_1\}$, $\{b_1,b_2\}$, $\{a_1,b_1,b_2\}$, $\{a_2,b_1,b_2\}$, $\{a_1,a_2,b_1,b_2\}$.  Therefore, we need at least three more queries as before.  In total, we need four queries.  The same argument applies when the first query is $b_2$.

If we take $k$ parallel copies of this poset, then it has $7^k$ antichains, and thus the proposed bound is $\lceil \log_2 7^k \rceil = 3k$. But, since each of the copies needs four queries, we need at least $4k$ queries.

Probably, there is a larger poset with larger gap.  But this argument can only improve the coefficient.

Here, the problem looks to be a situation where no query partitions the search space evenly.  In such a case, the adversary can force the larger half to remain.