# Memory-Enhanced Knowledge Reasoning with Reinforcement Learning
## 3 Reinforcement Learning Framework Algorithm Based on ConvR Embedding
### Reasoning Framework Algorithm
#### 3.3.5 Policy  
1. Dynamic policy space pruning  
Due to the fact that invalid paths are often more numerous than correct paths and are easier to detect, the burden of path search is increased, especially when the KG grows with the increase in path length, resulting in an exponential increase in action space and thus increasing the search burden. This phenomenon is even more severe for entities with large outdegrees (i.e., entities with many connecting relations). Enumerating all possible relation paths between entity pairs on a large-scale knowledge graph is infeasible, so conducting effective path exploration and identifying reasoning paths is particularly important. Therefore, we leverage the advantage of ConvR embedding to obtain, in the action space, all tail entities that are connected to the corresponding head entity and relation. Specifically, for the current entity and selected relation, we compute the probability of all entities becoming the tail entity and then select the top K entities as our action space, where K is predetermined for each dataset. A large K value may lead to information confusion, while a small K value may lead to insufficient information. Therefore, we can refine the action space to enable the goal to reach the target entity. 2. Policy network  
Each entity and relation in the knowledge graph (KG) are represented by a low-dimensional dense vector with semantic information through ConvR embeddings. In order to construct a search sequence more effectively, the agent needs to not only understand the current information but also the past events that have occurred. Therefore, we utilize the SLSTM algorithm proposed in this paper to encode the historical information of the search history \((e_{s},r_{1},e_{1},r_{2},\ldots e_{t})\) into a hidden state denoted as \(h_{t}\), representing the historical information at time step t. The output of the historical information is then passed through a self-attention layer. Assuming the initial state is \(h_{0}=0\), the search history \(h_{t}=(e_{s},r_{1},e_{1},r_{2},\ldots e_{t})\) is composed of the action sequence taken from step 1 to step t.  
\[h_{0}=SLSTM(0,r_{0}) \tag{17}\]  
\[h_{t}=SLSTM((h_{t-1},c_{t-1}),o_{t-1}) \tag{18}\]  
In the self-attention layer, we first set up a linear function \(f_{s}\), which should be twice the size of \(h_{t}\) due to the use of bidirectional SLSTM in reinforcement learning knowledge reasoning. \[f_{s}=f(h_{t}*h_{t},1) \tag{19}\]  
Then, we calculate the attention weights using the SoftMax function. \[a_{s}=softmax(f_{s}) \tag{20}\]  
Finally, we obtain the final output \(h_{t}\) by multiplying the attention weights with the linear function \(f_{s}\). \[h_{t}=a_{s}\cdot f_{s} \tag{21}\]  
The reinforcement learning policy \(\pi\), which maps state \(s_{t}\) to action space \(O_{t}\), can be represented as \(\pi:s_{t}\to O_{t}\), where \(O_{t}\in R^{|O_{t}|\times d_{1}}\) and \(d_{1}\) is the embedding dimension. \[\pi_{\theta}(o_{t}|s_{t})=\sigma\big{(}O_{t}\times W_{2}ReLU(W_{1}\big{[}e_{t };r_{q};h_{t}]\big{]}\big{)} \tag{22}\]  
where \(\sigma\) represents the SoftMax function, \"\(\cdot\)\" denotes the concatenation operation, \(W_{1}\in R^{(d_{1}+d_{2}+d_{3})\times d_{4}}\), \(W_{2}\in R^{d_{1}\times d_{4}}\), and \(d_{2}\) is the entity dimension, \(d_{3}\) is the dimension of historical hidden states, and \(d_{4}\) is the number of hidden units in the fully connected layer. Then, a dropout method is added to make the process more random. The upgraded strategy is expressed as follows:  
\[\tilde{\pi}_{\theta}(o_{t}|s_{t})=\pi_{\theta}(o_{t}|s_{t})\cdot m+\varepsilon \tag{23}\]where \(m\) is sampled from a Bernoulli distribution, which randomly masks some options in its action space. \(\varepsilon\) is a very small value when \(m=0\). 3.