Study on Using Reinforcement Learning for the Monotone Boolean Reconstruction

This paper investigates the feasibility of using reinforcement learning to solve combinatorial optimization problems, in particular, the problem of query-based monotone Boolean function reconstruction. The monotone Boolean function reconstruction problem is a typical combinatorial problem that reconstructs the function unambiguously with a minimum number of queries about the value of the function at the defined points, based on the monotonicity of the function. The Shannon complexity of the problem is of the order of 2^n/sqrt(n), and the solution algorithm relies on complex constructions, which also add complexity in the form of memory and time. Additionally, there are problems of partial reconstruction, e.g., in the mining of associative rules, which do not fit into the developed solution formats. This necessitates exploring heuristic domains to attract additional resources to solve the problem. To this end, all elements of reinforcement learning - environment, agent, policy, etc. - are designed, and both exact and approximate algorithms are given to perform the necessary structural data transformations, as well as to calculate the reward, the value, and other operational data of the algorithm. The focal point of the considerations is a subclass of monotone Boolean functions related to the well-known shadow minimization theorem of layer-by-layer characterized functions. Preliminary experiments have been started and they require follow-up intensive actions.