Answers.Body: <h6>RL approach</h6>
  <p>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.</p>
  <p>Anyway, if so, it seems more like <strong>bandit</strong> 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.</p>
  <ul>
  <li>Your reward function <span class="math-container">$r(s_t,a_t)=r(A_t) = y_t$</span>, where <span class="math-container">$y_t = f(x; A_t)$</span>.</li>
  <li>As you said you have two actions that define an interval <span class="math-container">$A_t=[a_t, b_t]$</span>; probably is better to predict an <em>offset</em>: say your range is <span class="math-container">$[-10, 10]$</span>, the agent predicts two offsets <span class="math-container">$\Delta_a,\Delta_b$</span> (both <span class="math-container">$&gt;0$</span>) such that <span class="math-container">$A_t=[\Delta_a-10,10-\Delta_b]$</span>.</li>
  </ul>
  <p>Since you obtain a sequence of <span class="math-container">$y_1,y_2,\ldots, y_t$</span> you may try to recover <span class="math-container">$P$</span> by averaging out the (Gaussian) noise <span class="math-container">$n$</span> if possible, and multiplying by <span class="math-container">$\Delta_t$</span> (computed from <span class="math-container">$A_t$</span>). If you're able to do this you can consider it as your current state, even it's not a proper state.</p>
  <blockquote>
  <p>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.</p>
  </blockquote>
  <p>Lastly, you may want to consider <strong>genetic algorithms</strong> (GA) and <em>simulated annealing</em> too.</p>
  <hr />
  <h6>Algorithmic approach</h6>
  <p>Are you sure that an algorithm based on <em>dynamic programming</em> (by working on a discretized range of intervals) or <em>divide-et-impera</em> won't work?</p>
  <p>I mean if you consider a grid <span class="math-container">$N\times N$</span> that discretizes the initial interval <span class="math-container">$[-10,10]$</span>, you can design an (inefficient) algorithm that loops over each <span class="math-container">$N^2$</span> combinations of intervals, evaluating <span class="math-container">$f(x)$</span>. Then, you keep track of the interval that achieves the higher <span class="math-container">$y_t$</span>, and that will be your (approximate) solution.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-05-08T15:46:51.660Z
Answers.Text: Thank you for your time and for your response. I am goint to try to attack it from bandit perspective. About the algorithmic approach it is true that is a way to solve, however as you said it is inneficient. I am trying to solve this problem efficiently and accuratly that is the reason I tried to find a broader framework like RL to implement classical methods like Q-learning to my problem.
Answers.UserDisplayName: miguelrc
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-05-08T14:54:23.730Z
Answers.LastActivityDate: 2023-05-08T14:54:23.730Z
Answers.UserDisplayName: Luca Anzalone
Body: <p>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.</p>
  <p>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.</p>
  <p>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 &quot;gridworld&quot; 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.</p>
  <p>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.</p>
  <p>EDIT:</p>
  <p>Suppose we have a noisy function <span class="math-container">$f(x)$</span> where <span class="math-container">$x\in[-10,10]$</span>. The idea is try to find the value <span class="math-container">$x^*$</span> which maximimize the function. For that, we can try <span class="math-container">$K$</span> different intervals <span class="math-container">$A_t=[a_t,b_t]$</span> with <span class="math-container">$t=1,\dots,K$</span>. For example <span class="math-container">$A_1 = [-1,0]$</span>, <span class="math-container">$A_2=[-10,0]$</span>, etc.</p>
  <p>For each tested interval we obtain a sample <span class="math-container">$y_t$</span> which depends on two factors:</p>
  <ol>
  <li>If the optimum <span class="math-container">$x^*$</span> is inside the interval, the average power of <span class="math-container">$y_t$</span> will be higher.</li>
  <li>The width of the interval, in other words, if <span class="math-container">$x^*=0.5$</span> and the tested interval si <span class="math-container">$[0,1]$</span>, the average power of <span class="math-container">$y_t$</span> will be higher than using <span class="math-container">$[-10,10]$</span>.</li>
  </ol>
  <p>The action space would be the intervals <span class="math-container">$A_t$</span> and the state space is my doubt. I thought about computing the posterior distribution of the parameter <span class="math-container">$x*$</span> and update after each new sample <span class="math-container">$y_t$</span>, therefore each state <span class="math-container">$S_t$</span> would be the posterior probability distribution computed with the samples <span class="math-container">$\{y_1,y_2,...,y_{t-1}\}$</span>. I mean <span class="math-container">$p_t(x^*|y_1,\dots,y_{t-1})$</span>.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-05-08T10:56:18.147Z
Comments.Text: What is the "interval" you mention?
Comments.UserDisplayName: Luca Anzalone
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-05-08T11:49:49.167Z
Comments.Text: What is your state space and action space?
Comments.UserDisplayName: Aray Karjauv
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-05-08T12:57:25.647Z
Comments.Text: Thank you for your responses. I have updated the explanation, i hope it clarifies the problem.
Comments.UserDisplayName: miguelrc
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-05-08T13:35:12.607Z
Comments.Text: Given an interval $A_t$, how do you evaluate $f(x)$? I mean you sample a value from the interval, i.e. $x\sim A_t$, then compute the function? I'm wondering whether the agent should also predict $x$..
Comments.UserDisplayName: Luca Anzalone
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-05-08T13:47:01.487Z
Comments.Text: Sorry. I deleted my previous comment because it was incorrect. The idea is evaluate the function piecewise in this manner:
  \begin{align} f(x) &= \frac{P}{\Delta_t} + n, \text{if}\ \ x^*\in A_t\\ f(x) &= n, \text{if}\ \ x^{*} \notin A_t \end{align}
  with $n$ gaussian noise $\Delta_t$ is the width of $A_t$ and $P$ the power of the source.
Comments.UserDisplayName: miguelrc
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-05-08T14:06:00.027Z
Comments.Text: Alright, so how do you know if $x^*\in A_t$? You can compute that?
Comments.UserDisplayName: Luca Anzalone
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-05-08T14:17:13.773Z
Comments.Text: No, we only get a sample $y_t$ which can be $\frac{P}{\Delta_t}+n$ if $x^*\in A_t$ and only noise if It is not inside. (Sorry if I havent explained propertly)
Comments.UserDisplayName: miguelrc
Tags: <reinforcement-learning>
Title: Is reinforcement learning the correct approach for power source location?
UserDisplayName: miguelrc
ThreadText: # Is reinforcement learning the correct approach for power source location?
  
  (Asked by: username_0 on 2023-05-08)
  
  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})$.
  
  **Tags:** reinforcement-learning
  > **Comments:**
  > **username_1**: What is the "interval" you mention?  
  > **username_2**: What is your state space and action space?  
  > **username_0**: Thank you for your responses. I have updated the explanation, i hope it clarifies the problem.  
  > **username_1**: Given an interval $A_t$, how do you evaluate $f(x)$? I mean you sample a value from the interval, i.e. $x\sim A_t$, then compute the function? I'm wondering whether the agent should also predict $x$..  
  > **username_0**: Sorry. I deleted my previous comment because it was incorrect. The idea is evaluate the function piecewise in this manner: \begin{align} f(x) &= \frac{P}{\Delta_t} + n, \text{if}\ \ x^*\in A_t\\ f(x) &= n, \text{if}\ \ x^{*} \notin A_t \end{align} with $n$ gaussian noise $\Delta_t$ is the width of $A_t$ and $P$ the power of the source.  
  > **username_1**: Alright, so how do you know if $x^*\in A_t$? You can compute that?  
  > **username_0**: No, we only get a sample $y_t$ which can be $\frac{P}{\Delta_t}+n$ if $x^*\in A_t$ and only noise if It is not inside. (Sorry if I havent explained propertly)  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-05-08. Score: 0
  
  ###### 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.
  
  > **Comments:**
  > **username_0**: Thank you for your time and for your response. I am goint to try to attack it from bandit perspective. About the algorithmic approach it is true that is a way to solve, however as you said it is inneficient. I am trying to solve this problem efficiently and accuratly that is the reason I tried to find a broader framework like RL to implement classical methods like Q-learning to my problem.  
  
  ---
  
  