Inverse reinforcement learning (IRL) attempts to use demonstrations of “expert” decision making in a Markov decision process to infer a corresponding policy that shares the “structured, purposeful” qualities of the expert's actions. In this paper, we extend the maximum causal entropy framework, a notable paradigm in IRL, to the infinite time horizon setting. We consider two formulations (maximum discounted causal entropy and maximum average causal entropy) appropriate for the infinite horizon case and show that both result in optimization programs that can be reformulated as convex optimization problems, thus admitting efficient computation. We then develop a gradient based algorithm for the maximum discounted causal entropy formulation that enjoys the desired feature of being model agnostic, a property that is absent in many previous IRL algorithms. We propose the stationary soft Bellman policy, a key building block in the gradient based algorithm, and study its properties in depth, which not only leads to theoretical insight into its analytical properties, but also helps motivate a large toolkit of methods for implementing the gradient based algorithm. Finally, we select three
15 May 2017 in International Journal of Data Science and Analytics
We consider the problem of dynamic allocation of a single server with batch processing capability to a set of parallel queues. Jobs from different classes cannot be processed together in the same batch. The arrival processes are mutually independent Poisson flows with equal rates. Batches have independent and identically distributed exponentially distributed service times, independent of the batch size and the arrival processes. It is shown that for the case of infinite buffers, allocating the server to the longest queue, stochastically maximizes the aggregate throughput of the system. For the case of equal-size finite buffers the same policy stochastically minimizes the loss of jobs due to buffer overflows. Finally, for the case of unequal-size buffers, a threshold-type policy is identified through an extensive simulation study and shown to consistently outperform other conventional policies. The good performance of the proposed threshold policy is confirmed in the heavy-traffic regime using a fluid model.
14 April 2021 in IEEE Journal on Selected Areas in Information Theory
Consider N cooperative but non-communicating players where each plays one out of M arms for T turns. Players have different utilities for each arm, represented as an N×M matrix. These utilities are unknown to the players. In each turn, players select an arm and receive a noisy observation of their utility for it. However, if any other players selected the same arm in that turn, all colliding players will receive zero utility due to the conflict. No communication between the players is possible. We propose two distributed algorithms which learn fair matchings between players and arms while minimizing the regret. We show that our first algorithm learns a max-min fairness matching with near- O(logT) regret (up to a loglogT factor). However, if one has a known target Quality of Service (QoS) (which may vary between players) then we show that our second algorithm learns a matching where all players obtain an expected reward of at least their QoS with constant regret, given that such a matching exists. In particular, if the max-min value is known, a max-min fairness matching can be learned with O(1) regret.
In this paper, we study the optimal control of service rates of a tandem queue with power constraints. The service rate of a server is determined by the power allocated to that server. The total power of the system is fixed. The system cost is comprised of two parts, the holding cost reflecting the congestion of queues and the operating cost reflecting the power consumed at servers. The optimization objective is to find the optimal power allocation policy among servers, which can minimize the system average cost. We formulate this problem as a Markov decision process with a constrained action space. Sensitivity-based optimization theory is applied to study this problem. The necessary and sufficient condition of optimal service rates, and the optimality of the vertexes of the feasible domain are derived when the operating cost has a linear or concave form. An iterative algorithm is further developed to find the optimal service rates. This algorithm may work well even when the cost function has a general form. The extension to general tandem queues with many servers is also studied. Finally, we conduct numerical experiments under different parameter settings to demonstrate the main idea of this paper.