Is reinforcement learning the correct approach for power source location?

Question

I am trying to attack a problem for my thesis and I feel RL is the correct framework for this problem, however I am completely new to this topic and I am not sure about it.

The idea of the problem is to locate the position of a power source, in order to obtain the position I can perform several questions asking if the source is located in that interval. If the source is inside the interval I will obtain higher power, in other case the received power will be lower (stochastically). Additionally, if the interval is greater or smaller the received power change, the most narrow the interval the greater the power.

In my personal opinion the problem fits quite well the idea of reinforcement learning of discovering an environment by an agent. However, I do know how to model the rewards (maybe with the received power). Finally, the biggest problem is related to the states, in the RL literature I read about "gridworld" or similar problems but in my case I do not feel comfortable defining the state space. I thought about compute the posterior distribution in a Bayesian sense and using that distribution as state.

Thank you in advance and sorry for my English. If you have some recommendation about RL literature to strong my knowledge I would appreciate it.

EDIT:

Suppose we have a noisy function $f(x)$ where $x\in[-10,10]$. The idea is try to find the value $x^*$ which maximimize the function. For that, we can try $K$ different intervals $A_t=[a_t,b_t]$ with $t=1,\dots,K$. For example $A_1 = [-1,0]$, $A_2=[-10,0]$, etc.

For each tested interval we obtain a sample $y_t$ which depends on two factors:

1. If the optimum $x^*$ is inside the interval, the average power of $y_t$ will be higher.
2. The width of the interval, in other words, if $x^*=0.5$ and the tested interval si $[0,1]$, the average power of $y_t$ will be higher than using $[-10,10]$.

The action space would be the intervals $A_t$ and the state space is my doubt. I thought about computing the posterior distribution of the parameter $x*$ and update after each new sample $y_t$, therefore each state $S_t$ would be the posterior probability distribution computed with the samples $\{y_1,y_2,...,y_{t-1}\}$. I mean $p_t(x^*|y_1,\dots,y_{t-1})$.

Answer 1

RL approach

I guess this problem has not a clear definition of a state space, unless you can describe the power source by some features that change in time.

Anyway, if so, it seems more like bandit problem rather than RL. As I understand, the hidden location of the power source remains the same during time, so it's like having only an initial state.

• Your reward function $r(s_t,a_t)=r(A_t) = y_t$, where $y_t = f(x; A_t)$.
• As you said you have two actions that define an interval $A_t=[a_t, b_t]$; probably is better to predict an offset: say your range is $[-10, 10]$, the agent predicts two offsets $\Delta_a,\Delta_b$ (both $>0$) such that $A_t=[\Delta_a-10,10-\Delta_b]$.

Since you obtain a sequence of $y_1,y_2,\ldots, y_t$ you may try to recover $P$ by averaging out the (Gaussian) noise $n$ if possible, and multiplying by $\Delta_t$ (computed from $A_t$). If you're able to do this you can consider it as your current state, even it's not a proper state.

If you frame the problem as a bandit task, if I recall correctly, you don't need a state at all because you only care about the actions.

Lastly, you may want to consider genetic algorithms (GA) and simulated annealing too.

---

Algorithmic approach

Are you sure that an algorithm based on dynamic programming (by working on a discretized range of intervals) or divide-et-impera won't work?

I mean if you consider a grid $N\times N$ that discretizes the initial interval $[-10,10]$, you can design an (inefficient) algorithm that loops over each $N^2$ combinations of intervals, evaluating $f(x)$. Then, you keep track of the interval that achieves the higher $y_t$, and that will be your (approximate) solution.

Maybe you can star from such simple description to design something more sophisticated, or even implement both approaches and compare them to see which is the winning method.