# Reinforcement Learning Based Query Routing Approach for P2P Systems
## 3 RLQR Approach
### 1-Neighbor-Selection Algorithms
#### 3.2.3 Tsns: Thompson Sampling-Based 1-NS Algorithm  
Thompson sampling (TS) [27] is an efficient algorithm used for addressing the exploration/exploitation trade-off in different research areas and especially for solving the MAB problem. In this respect, we extend the idea of Thompson sampling to define our TSNS algorithm for solving the 1-NS problem. Indeed, we assume that each neighbor \(n_{i}\in\{n_{1},\ldots,n_{m}\}\) yields a success (i.e., a reward of 1) with probability \(\theta_{i}\in[0,1]\) and produces a failure (i.e., a reward of 0) with probability \(1-\theta_{i}\). The success probabilities \((\theta_{1},\ldots,\theta_{m})\) of the \(m\) neighbors are unknown to the forwarder peer (i.e., the learner), but are fixed over time, and therefore can be learned from previous queries. We suppose that the learner starts with an independent prior belief over each \(\theta_{i}\) and this latter is beta-distributed with parameters \(\alpha_{i}\) and \(\beta_{i}\), which denote the number of times \(n_{i}\) produces a reward of 1 (success) or a reward of 0 (failure), respectively. Therefore, the prior Probability Density Function (PDF) of the probability of success \(\theta_{i}\) of each neighbor \(n_{i}\in\{n_{1},\ldots,n_{m}\}\) is calculated as follows:  
\[p(\theta_{i})=\frac{\Gamma(\alpha_{i}+\beta_{i})}{\Gamma(\alpha_{i})\Gamma( \beta_{i})}\theta_{i}^{\alpha_{i}-1}(1-\theta_{i})^{\beta_{i}-1}, \tag{1}\]  
here \(\Gamma\) denotes the gamma function. It is worth mentioning that whenever a neighbor is selected and its reward is observed the distribution is updated according to [PERSON] rule. The main idea of TSNS is to choose a neighbor according to its probability of being the best one. To do so, TSNS initially assumes that each neighbor \(n_{i}\) to have prior \(Beta(\alpha,\beta)\), where \(\alpha=\beta=1\), on \(\theta_{i}\) (see initialization part in Algorithm 3). It then samples a success probability estimate \(\hat{\theta_{i}}\) of each neighbor \(n_{i}\) from its posterior distributions of \(\theta_{i}\), which is a beta distribution with parameters \(\alpha_{i}\) and \(\beta_{i}\) (see lines 1-5 Algorithm 3). Thereafter, it selects, for the query \(q_{t}\), the neighbor \(n_{i}(q_{t})\) with the largest estimate \(\hat{\theta_{i}}\) (see line 7 Algorithm 3). Finally, after receiving the reward \(r_{i}(q_{t})\), TSNS updates the distribution parameters \(\alpha_{i}\) and \(\beta_{i}\) of the selected neighbor \(n_{i}(q_{t})\) (see lines 9-11 Algorithm 3).
```
0:\(q_{t}\): search query at trial \(t\). \(N=\{n_{1},\ldots,n_{m}\}\): set of neighbors \(\alpha=(\alpha_{1},\ldots,\alpha_{m})\): alpha parameters of the \(m\) neighbors \(\beta=(\beta_{1},\ldots,\beta_{m})\): beta parameters of the \(m\) neighbors \(n_{i}(q_{t})\): the neighbor to be selected for \(q_{t}\)
0:\(\alpha=(1,\ldots,1)\) \(\beta=(1,\ldots,1)\)
1:for all\(n_{i}\in N\)do
2: sample \(\hat{\theta_{i}}=Beta(\alpha_{i},\beta_{i})\)
3:endfor
4:\(n_{i}(q_{t})=\operatorname*{argmax}_{n_{i}\in N}\hat{\theta_{i}}\)
5:\(\alpha_{i}=\alpha_{i}+r_{n_{i}}(q_{t})\)
6:\(\beta_{i}=\beta_{i}+r_{n_{i}}(q_{t})\)
```
**Algorithm 3** TSNS: Thompson sampling-based 1-NS algorithm