Stochastic Optimization
Prof. Rui Wang · LASSO Research Group
My main research vision is to establish an efficient and general algorithm design framework via Markov Decision Process (MDP), such that the scope of algorithm design for wireless and computing resource allocation can be extended. MDP is a powerful tool for the optimization along a sequence of time slots (stages), where an average total cost is minimized. However, its applications in wireless systems or computing systems usually suffer from the curse of dimensionality. For instance, the key to solve an MDP problem is to evaluate its value function for all possible system states, and the number of system states usually grow exponentially with respect to the number of users in the system. Current approximate approaches, like deep reinforcement learning, is general for the MDP applications in almost all areas. They do not exploit the well-formulated structure of the communication or computing systems. Hence, it is of great interests to design more efficient and insightful solution algorithms for MDP in communication or computing systems.
My first attempt in this direction is to propose a decomposition method for value function such that it can be approximated as a linear combination of local value functions. It reduces the exponential computation complexity and memory requirement to linear, and also facilitate semi-distributive scheduler design. This approach can be widely applied in delay-aware scheduling of wireless networks and computing systems. However, the local value functions have no analytical expressions, and have to be evaluated via iterative algorithm.
Hence, my follow-up attempt is to develop analytical approximation method for value function, whose gaps to the true value function or performance gap to the optimal solution can be bounded tightly. My latest progress demonstrates its feasibility. To date, I have developed methods with analytical approximate value function for the optimization with infinite or random number of stages. The application scenarios include: (1) joint popular file placement and deliver in a cache-enabled cellular network; (2) downlink video streaming in massive MIMO networks; (3) mobile-edge computing systems. None of the above demonstration scenarios can be addressed via the existing methods, as some practical considerations are included. For example, in the first scenario, I address the resource allocation with finite file lifetime. In the following two scenarios, I consider the random arrival and departure of requesting users, as each user requests on finite transmission resource from the BS. Note that in the conventional algorithm design method, the dynamics of requesting users update are hard to be exploited.
