Consider an input set of vertices $V$ and vertices $s,t\in V$. The goal is to learn some unknown shortest path from $s$ to $t$; the set of edges of the graph is hidden at first and there may be multiple shortest paths.
At each iteration, each vertex is randomly colored using $0$ or $1$. We then get a single bit, that is $1$ with a probability proportional to the number of $1$-vertices along the path. That is, if $6$ of the vertices along the path were colored with $1$ and $4$ were zero, then the bit will be $1$ w.p. 3/5.
Importantly, we get to know the coloring of every iteration, and the goal path does not change.
How many samples do we need until we can compute the path with, say, probability 2/3?
A very simplistic approach would be to eliminate all monochromatic paths whose color is different than the given bit (e.g., a $1$-path can be eliminated if we get a $0$-bit). This seems to give a very weak bound.