High dimensionality of model-based Reinforcement Learning and Markov Decision Processes can be reduced using abstractions of the state and action spaces. Although hierarchical learning and state abstraction methods have been explored over the past decades, explicit methods to build useful abstractions of models are rarely provided. In this work, we provide a new state abstraction method for solving infinite horizon problems in the discounted and total settings. Our approach is to progressively disaggregate abstract regions by iteratively slicing aggregations of states relatively to a value function. The distinguishing feature of our method, in contrast to previous approximations of the Bellman operator, is the disaggregation of regions during value function iterations (or policy evaluation steps). The objective is to find a more efficient aggregation that reduces the error on each piece of the partition. We provide a proof of convergence for this algorithm without making any assumptions about the structure of the problem. We also show that this process decreases the computational complexity of the Bellman operator iteration and provides useful abstractions. We then plug this state space disaggregation process in classical Dynamic Programming algorithm namely Approximate Value Iteration, Q-Value Iteration and Policy Iteration. Finally, we conduct a numerical comparison on randomly generated MDPs as well as classical MDPs. Those experiments show that our policy-based algorithm is faster than both traditional dynamic programming approach and recent aggregative methods that use a fixed number of adaptive partitions.

This paper addresses the problem of an aerial moving target search with a radar on an airborne platform.An observation of the radar is modeled as a cone covering a set of regions of the search area.We assume overlapping cones of observation, and we want to find the discrete allocation plan of search effort to the cones in order to optimize target detection.For the stationary target search with overlapping cones, we present a dynamic programming algorithm that computes the optimal allocation.An approximate greedy heuristic, which is more appropriate in a real time context, is also presented and assessed.The moving target search problem is solved with the Forward And Backward (FAB) algorithm coupled with the different stationary search algorithms.In this paper, we use a radar detection model that has been shown to be more realistic than the ones usually considered.Also, several models of movement of the target are considered with different Markovian transition matrices.We compare the performance of the mentioned algorithms on several scenarios.

This paper addresses the problem of a moving target search with a discrete allocation of search effort to disjoint cones of observation. A cone covers several regions with different visibilities. This is an important step towards the optimal search with radars on airborne platforms which has not been previously studied. We adapt Forward And Backward (FAB) algorithms to this problem and apply them to compute search plans. We measure the quality of our solution with a continuous relaxation of the problem. In a set of numerical experiments we exhibit that our algorithms have good performance in terms of plan quality and computation time. Finally, we compare the plans optimizing different objective functions.

As today’s networking systems utilise more virtual-isation, efficient auto-scaling of resources becomes increasingly critical for controlling both the performance and energy consumption. In this paper, we study the techniques to learn the optimal auto-scaling policies in a distributed network when parts of the system dynamics are unknown. Reinforcement Learning methods have been applied to solve auto-scaling problems. However they can run into computational and convergence issues as the problem scale grows. On the other hand, distributed networks have relational structures with local dependencies between physical and virtual resources. We can exploit these structures to overcome the convergence issues by using a factored representation of the system.We consider a distributed network in the form of a tandem queue composed of two nodes. The objective of the auto-scaling problem is to find policies that have a good trade-off between quality of service (QoS) and operating costs. We develop a factored Reinforcement Learning algorithm, named FMDP online, to find the optimal auto-scaling policies. We evaluate our algorithm with a simulated environment. We compare it with existing Reinforcement Learning methods and show its relevance in terms of policy efficiency and convergence speed.

Reducing the energy consumption of a cloud system while guaranteeing a given quality of service level is a crucial problem encountered today by cloud providers. We consider an auto-scaling model where virtual machines are turned on and off depending on the queue's occupation (or thresholds). This model represents the variability of allocated resources (Virtual Machines or VMs) according to user demands. It can be studied using an hysteresis queuing model, which is represented by a multidimensional Markov chain, whose calculation of the stationary distribution becomes complex when the number of VMs grows. We adopt a cost-aware approach and define a mean cost computed as a reward function on the stationary distribution. This cost takes into account both the performance (for Service Level Agreement: SLA) and the use of the resources (for Energy). We propose efficient optimisation methods to find threshold values minimising the global cost. Because this mean cost is a non-convex function, the research of the optimal value is complex. We propose different optimisation methods: the first one, based on heuristics, coupled with aggregation of the Markov Chain to reduce the execution time and the second one which is a meta heuristic: the Simulated Annealing. Finally, we present a real case of a cloud system that we model and set parameter values to test our optimisation algorithms and show their relevance.

In this paper, we deal with a dynamic and stochastic admission control and mobile association problem in an heterogeneous wireless network. We extend the usual problem by adding mobility features described by a Markov Modulated Poisson Process. The aim is to optimize the average performance of the system. This dynamic control problem is modeled and solved using a Semi Markov Decision Process (SMDP) framework. We then assess the impact of the mobility and show that (i) our network centric approach outperforms a simple user centric algorithm and (ii) mobility improves the performance of the system when optimal policy of the problem is used.

In this paper, we deal with a control problem for a new joint admission and resource allocation controller taking into account vertical handover in a heterogeneous wireless network. The controller is dynamic: it uses statistical information on the arrival and sojourn rates of the mobiles to optimize the average performance of the system. To account for multi-objective optimization, we consider the maximization of an objective subject to a set of constraints. We turn this constrained problem into an unconstrained one that we numerically solve using the Semi-Markovian Decision Process (SMDP) framework. We compare the optimal policy to some heuristics for different parameter values.

We consider a single-server queue in discrete time, in which customers must be served before some limit sojourn time of geometrical distribution. A customer who is not served before this limit leaves the system: it is impatient. The service of customers, the loss due to impatience and the holding of customers in the queue induce costs. The purpose is to decide when to serve the customers so as to minimize them. We use a Markov decision process with infinite horizon and discounted cost. We establish the structural properties of the stochastic dynamic programming operator and we deduce that the optimal policy is of threshold type. In addition, we are able to compute explicitly the optimal value of this threshold in terms of the parameters of problem.