# An Intelligent Method for C++ Test Case Synthesis Based on a Q-Learning Agent
## 2 Materials and Methods
### Agent's State Representation  
In reinforcement learning, the quality of decisions made depends on the representation of the state, which serves as the basis for estimating the utility of actions. However, in tasks involving complex software environments, such as test case synthesis for C++ libraries, the curse of dimensionality becomes a critical concern, as the number of potential states can grow exponentially with the complexity of API usage which a phenomenon often referred to as the state explosion problem [6]. To reduce the complexity, the state \(s_{t}\) is limited as follows.  
TC Suffix Function. Let there be a current sequence of API calls of the tested library representing a partially synthesized TC at step t:  
\[TC^{t}=\langle a_{1},a_{2},\ldots,a_{t}\rangle,\ \ a_{i}\epsilon\mathcal{A}\]  
Let \(k\in\mathbb{N}\) be the depth of the call history, then the abstract agent state is determined solely based on the last \(k\) actions using the test case suffix function:  
\[s_{t}=Suffix_{k}(S^{t})=\begin{cases}\oslash,&if\ t=0\\ \langle a_{1},\ldots,a_{t}\rangle&if\ 0<t\leq k\\ \langle a_{t-k+1},\ldots,a_{t}\rangle&if\ t>k\end{cases} \tag{2}\]  
Each call is encoded as a record that abstracts away syntactic details but retains the type of the object, function name, call category, and argument signature. Given a partially synthesized test case in state \(s_{t}\), the state abstraction is computed using a suffix function of the TC. This limited representation is not fully Markovian in the classical sense. Specifically, it does not contain complete information about argument values, internal object states, or the global execution context that may influence the behavior of a function. Two sequences with the same function names but different arguments will be represented by the same state key. The lack of detailed information on object state changes also leads to the loss of part of the dynamic context. Despite the loss of full Markovian properties, empirical results show that this abstraction is sufficient for effective learning in the task of synthesizing TCs with limited length. Within such local heuristics, the compact representation may enable high learning speed, avoids excessive state-space branching, and prevents excessive memory usage. Also, unlike solutions that require full simulation of the program state or tracking object states, this representation can enable scaling to large APIs without a loss of efficiency. Moreover, such an abstraction makes the implementation stable, controllable, and interpretable, which is especially valuable in CI systems where the transparency of test suite synthesis is crucial. Therefore, this representation offers a rational compromise between accuracy, generalization, and computational efficiency, which is essential for practical tasks of test code generation for C++ libraries.  
The Q-table is used as a model for approximating the utility function \(Q(s,a)\). Each key in the Q-table is derived using the TC suffix function Equation (2) applied to the partially constructed TC during agent training. The action space \(\mathcal{A}\) includes the set of admissible API calls determined based on the currently available objects and functions in the current state. Each action in the action space is associated with a numerical value of the Q-function representing the expected cumulative reward when this action is selected in the given state. Each element in the Q-table functions as a node from which edges emerge toward possible TC extensions through action selection from the \(\mathcal{A}\).