# Visual Tracking Using Wang-Landau Reinforcement Sampler
## 3 Proposed Visual Tracking System
### Reinforcement Learning for Visual Tracking  
In this study, \(p^{*}(\mathbf{X}_{t}|\mathbf{X}_{t-1})\) in (5) is implemented by selecting the optimal action \(a_{t}\) in a reinforcement learning framework, in which \(\mathbf{X}_{t+1}\sim a_{t}(\cdot|\mathbf{X}_{t})\). We compute the reward \(\mathcal{R}\) by measuring the improvement in the log-posterior probability in (2), as follows:  
\[\mathcal{R}(s_{t},a_{t},s_{t+1})=\log p(\mathbf{X}_{t}|\mathbf{Y}_{1:t})-\log p (\mathbf{X}_{t+1}|\mathbf{Y}_{1:t+1}), \tag{6}\]  
where \(s_{t}=\{\mathbf{X}_{1:t}\}\). In (6), \(s_{t},s_{t+1}\in\mathcal{S}\) and \(a_{t}\in\mathcal{A}\), where \(\mathcal{S}\) and \(\mathcal{A}\) denote the spaces of states and actions, respectively. \(\mathcal{A}\) can have four possible actions, \(\{a^{left},a^{right},a^{up},a^{down}\}\):  
\[\mathcal{A}=\begin{cases}a^{left}:p_{x}\to p_{x}-1,p_{y}\to p_{y},\\ a^{right}:p_{x}\to p_{x}+1,p_{y}\to p_{y},\\ a^{up}:p_{y}\to p_{y}-1,p_{x}\to p_{x},\\ a^{down}:p_{y}\to p_{y}+1,p_{x}\to p_{x},\end{cases} \tag{7}\]  
where \(p_{x}\) and \(p_{y}\) are the pixel indexes at the \(x\) and \(y\) axes, respectively.  
Our visual tracker aims to find the optimal policy \(\pi^{*}:\mathcal{S}\to\mathcal{A}\) that maximizes the expected future reward at time \(t\):  
\[\pi^{*}=\operatorname*{arg\,max}_{\pi}\mathbb{E}_{\pi}\left[\mathcal{R}_{t+1} +\gamma\mathcal{R}_{t+2}+\gamma^{2}\mathcal{R}_{t+3}+\cdots+\gamma^{\tau-t-1} \mathcal{R}_{\tau}\right], \tag{8}\]  
for a single episode of length \(\tau\), where \(\gamma<1\) is a discounting parameter that weights rewards that can be received immediately. The expected cumulative reward in (8) is efficiently implemented by Q-learning [35] with the following updating rule:  
\[Q(s_{t},a_{t})\gets Q(s_{t},a_{t})+\alpha\left[\mathcal{R}_{t+1}+\gamma \underset{a}{\text{max}}Q(s_{t+1},a)-Q(s_{t},a_{t})\right], \tag{9}\]  
where \(\gamma\underset{a}{\text{max}}Q(s_{t+1},a)-Q(s_{t},a_{t})\) indicates the maximum update of the action-value function \(Q(s_{t},a_{t})\) at time \(t\). This update is caused by a state change from \(s_{t}\) to \(s_{t+1}\) through action \(a\). In (9), \(\mathcal{R}_{t+1}\) is the reward at time \(t+1\) and \(\alpha\) is a weighting parameter.  
The optimal policy in (8) can be determined toward maximizing the \(Q\)-values:  
\[\pi^{*}(\cdot|s)=\operatorname*{arg\,max}_{a}Q(s,a), \tag{10}\]  
where the next action \(a_{t+1}\) is sampled by \(\pi^{*}(a_{t}|s_{t})\) and the next state \(s_{t+1}\) is determined by (7). However, when using (10), there is a risk of choosing suboptimal actions because we select an action that maximizes only a current action value. This problem causes our visual tracker to explore only already-visited states, which become trapped in the local optimum.  
We overcome this problem by proposing the \(\epsilon\)-_greedy_ algorithm, in which we usually select an action that maximizes a current action-value; with a probability \(\epsilon\), we choose an action at random. This \(\epsilon\)-_greedy_ algorithm can be expressed as  
\[a\sim\begin{cases}\operatorname*{arg\,max}_{a}Q(s,a),&\text{with probability }1-\epsilon\\ random(\mathcal{A})&\text{with probability }\epsilon,\end{cases} \tag{11}\]  
where \(random(\mathcal{A})\) returns an action randomly. However, one of the difficulties we may experience when using \(\epsilon\)-_greedy_, as a result of randomness in (11), is the surplus of actions, which complicates optimal solution identification. Therefore, we propose a semirandom strategy based on the Wang-Landau algorithm [7], in which we control the randomness of policy using statistics on the number of visits in a particular state. This approach will be further explained in the following section.