Online learning in wireless networks via directed graph lifting transform

Due to the complexity of wireless network operations, estimation of cost-to-go functions requires a large number of observations and is impractical in many real-world networks. In this paper, a novel framework for the online learning of cost-to-go functions using a local wavelet transform is presented. The proposed technique allows a considerable reduction in the number of observations needed for accurate estimation. The approach is based on the representation of the trajectory of the logical state of the network as a graph. The observed state trajectory (and thus cost trajectory) is projected onto a subset of the nodes to construct a small graph summarizing paths of the overall graph. Low-complexity local lifting transform operations, then, are used to recover the cost-to-go function on the whole graph. Numerical results for a wireless network with ~ 1000 states show that the estimation error of the proposed technique is decreased by ~ 50% in the early stages of learning with respect to standard Q-learning.