# How to efficiently bias future samples?

My goal is to hit all of my 'targets' through a random variable $$Y : [0,1] \rightarrow \mathbb{R}$$. An explicit form of $$Y$$ is unknown but I am able to take a sample point as pass it to $$Y$$ and get its output.

Specifically, I am initially sampling points uniformly on $$[0,1]$$. For each sampled point $$x_j$$ I can compute $$Y(x_j)$$ easily (and repeated evaluations of the same $$x_j$$ will give the same output). I also know that outputs should be close with respect to input: $$\mathbb{P}[Y(x_i) = Y(x_j)]$$ should be roughly proportional to $$|x_i - x_j|$$.

Suppose $$\{ T_j : 1 \leq j \leq m\}$$ are my targets. I know that my random variable will necessarily map to one of these targets: $$Y(x) = T_j$$ for some $$j$$ and every $$x \in [0,1]$$. I want to sample until all my targets have been achieved in the sense that $$\{ T_1, \dots, T_m \} \subseteq \{ Y(x_1), \dots, Y(x_n)\}$$. Once I know of one point $$x_j$$ that maps to $$T_k$$, I no longer care about any future sampled point that also maps to $$T_k$$. Further, the labels of the targets are arbitrary; for example $$T_1$$ is no closer or further from $$T_2$$ than it is from $$T_{126}$$.

In order to minimize $$n$$, I want to bias my sampling so that successive samples are 'far away' from the values that were successful, for example if $$Y(x_1) = T_1$$, I want to actively avoid the region around $$x_1$$ since it is likely that nearby points also map to $$T_1$$. An idea I had regarding this is to do a sort of reverse kernel density estimate, whereby I can create a density $$f$$ based on the first point that hits a target and sample from a normalized version of $$\max(1 - f, 0)$$.

I'm not super familiar with sampling techniques, so if anyone can direct me to some theory that can do what I am seeking it would be greatly appreciated. I am also open to totally different methods of solving my problem.

• The problem doesn't quite make sense yet. What's the relationship between the value of $X(x)$ (which, by the way, would be much clearer as $f(x)$) and whether or not a particular $x$ value is in $T$? Are the $T$ the local maxima of $X(x)$, or something?
– Eoin
Commented Mar 6, 2022 at 22:48
• It's also not clear what "achieving a target" or "success" mean here.
– Eoin
Commented Mar 6, 2022 at 22:52
• Depending on what you're actually trying to do, the solution may be to look at applications of Gaussian Processes to reinforcement learning, e.g. gdmarmerola.github.io/ts-for-bayesian-optim
– Eoin
Commented Mar 6, 2022 at 22:53
• Thanks for the resource. I agree that my question is somewhat broad and perhaps ill-posed. There is no 'hard' relationship between $X(x)$ and $T$. The exact relationship is highly sensitive to the input. The only knowledge I know is that for values in a neighborhood of $x$, $X$ will map them to the same target with some high but unknown. Commented Mar 6, 2022 at 23:00
• So each time you evaluate $X(x)$, it tells you which of the targets that value of $x$ is closest to?
– Eoin
Commented Mar 6, 2022 at 23:02

Begin with uniform distribution $$U_0$$ on $$[0,1]$$.

Define a suitable value for $$0 < \epsilon <1$$, and $$0 < \alpha < 1$$.

randomly choose $$x_1$$, $$x_2$$ .. until you hit a target.

If from $$x_i$$ you hit a target, just decrease the probability density by alpha on $$[x_i - \epsilon, x_i + \epsilon] \cap [0,1]$$ and increase every where else in $$[0,1]$$ so that you still have a total probability of one. The new probability is $$U_1$$.

Pick other $$x_i$$ under $$U_1$$, and repeat until you hit a target. Following the same plan, you'll get $$U_2$$, and so on.

Little by little, your probability will concentrate on places where you did'nt found a $$x$$ that leads to a target. But you may still, with a lower probability pick a $$x$$ near one other that leads to a taget. If you really want to avoid that, then choose $$\alpha = 1$$.

By experiment, you will be able to tune $$\epsilon$$ and $$\alpha$$ so that you hit the greatest number of target in the shortest time (I suppose this is what you want to do).