Multi-agent systems (MAS) are central to applications such as swarm robotics and traffic routing, where agents must coordinate in a decentralized manner to achieve a common objective. Stochastic Shortest Path (SSP) problems provide a natural framework for modeling decentralized control in such settings. While the problem of learning in SSP has been extensively studied in single-agent settings, the decentralized multi-agent variant remains largely unexplored. In this work, we take a step towards addressing that gap. We study decentralized multi-agent SSPs (Dec-MASSPs) under linear function approximation, where the transition dynamics and costs are represented using linear models. Applying novel symmetry-based arguments, we identify the structure of optimal policies. Our main contribution is the first regret lower bound for this setting based on the construction of hard-to-learn instances for any number of agents, $n$. Our regret lower bound of $\Omega(\sqrt{K})$, over $K$ episodes, highlights the inherent learning difficulty in Dec-MASSPs. These insights clarify the learning complexity of decentralized control and can further guide the design of efficient learning algorithms in multi-agent systems.

The efficiency of business processes relies on business key performance indicators (Biz-KPIs), that can be negatively impacted by IT failures. Business and IT Observability (BizITObs) data fuses both Biz-KPIs and IT event channels together as multivariate time series data. Forecasting Biz-KPIs in advance can enhance efficiency and revenue through proactive corrective measures. However, BizITObs data generally exhibit both useful and noisy inter-channel interactions between Biz-KPIs and IT events that need to be effectively decoupled. This leads to suboptimal forecasting performance when existing multivariate forecasting models are employed. To address this, we introduce AutoMixer, a time-series Foundation Model (FM) approach, grounded on the novel technique of channel-compressed pretrain and finetune workflows. AutoMixer leverages an AutoEncoder for channel-compressed pretraining and integrates it with the advanced TSMixer model for multivariate time series forecasting. This fusion greatly enhances the potency of TSMixer for accurate forecasts and also generalizes well across several downstream tasks. Through detailed experiments and dashboard analytics, we show AutoMixer's capability to consistently improve the Biz-KPI's forecasting accuracy (by 11-15%) which directly translates to actionable business insights.

Clustering is a widely used unsupervised learning tool with applications in numerous real-world problems. Traditional clustering methods can result in highly skewed clusters where one cluster is notably larger than others, rendering them unsuitable for scenarios such as logistics and routing. In response, capacitated clustering approaches have emerged over the past decade. These approaches limit the number of data points each cluster can accommodate, thus resulting in more uniform cluster formations. In an online version of capacitated clustering, the algorithm must make an irrevocable decision for each incoming data point, determining whether to establish it as a new center or allocate it to existing centers. The goal is to minimize the count of opened centers while adhering to capacity constraints and achieving a satisfactory approximation of the clustering cost compared to the optimal solution. Although exploring online capacitated clustering remains uncharted, we are the first to propose a probabilistic Capacitated Online Clustering Algorithm (called COCA) for h-dimensional euclidean spaces. We theoretically bound the number of centers opened and provide constant cost approximation guarantees. Additionally, we conduct rigorous experiments to validate the computational efficacy of the proposed approaches.

This work considers multiple agents traversing a network from a source node to the goal node. The cost to an agent for traveling a link has a private as well as a congestion component. The agent’s objective is to find a path to the goal node with minimum overall cost in a decentralized way. We model this as a fully decentralized multi-agent reinforcement learning problem and propose a novel multi-agent congestion cost minimization (MACCM) algorithm. Our MACCM algorithm uses linear function approximations of transition probabilities and the global cost function. In the absence of a central controller and to preserve privacy, agents communicate the cost function parameters to their neighbors via a time-varying communication network. Moreover, each agent maintains its estimate of the global state-action value, which is updated via a multi-agent extended value iteration (MAEVI) sub-routine. We show that our MACCM algorithm achieves a sub-linear regret. The proof requires the convergence of cost function parameters, the MAEVI algorithm, and analysis of the regret bounds induced by the MAEVI triggering condition for each agent. We implement our algorithm on a two node network with multiple links to validate it. We first identify the optimal policy, the optimal number of agents going to the goal node in each period. We observe that the average regret is close to zero for 2 and 3 agents. The optimal policy captures the trade-off between the minimum cost of staying at a node and the congestion cost of going to the goal node. Our work is a generalization of learning the stochastic shortest path problem.

We consider the problem of cost-optimal utilization of a crowdsourcing platform for binary, unsupervised classification of a collection of items, given a prescribed error threshold. Workers on the crowdsourcing platform are assumed to be divided into multiple classes, based on their skill, experience, and/or past performance. We model each worker class via an unknown confusion matrix, and a (known) price to be paid per label prediction. For this setting, we propose algorithms for acquiring label predictions from workers, and for inferring the true labels of items. We prove that (i) our algorithms satisfy the prescribed error threshold, and (ii) if the number of (unlabeled) items available is large enough, the algorithms incur a cost that is near-optimal. Finally, we validate our algorithms, and some heuristics inspired by them, through an extensive case study.

We consider the problem of learning linear classifiers when both features and labels are binary. In addition, the features are noisy, i.e., they could be flipped with an unknown probability. In Sy-De attribute noise model, where all features could be noisy together with same probability, we show that 0-1 loss (l0−1) need not be robust but a popular surrogate, squared loss (lsq) is. In Asy-In attribute noise model, we prove that l0−1 is robust for any distribution over 2 dimensional feature space. However, due to computational intractability of l0−1, we resort to lsq and observe that it need not be Asy-In noise robust. Our empirical results support Sy-De robustness of squared loss for low to moderate noise rates.

Thompson Sampling has generated significant interest due to its better empirical performance than upper confidence bound based algorithms. In this paper, we study Thompson Sampling based algorithm for Unsupervised Sequential Selection (USS) problem. The USS problem is a variant of the stochastic multi-armed bandits problem, where the loss of an arm can not be inferred from the observed feedback. In the USS setup, arms are associated with fixed costs and are ordered, forming a cascade. In each round, the learner selects an arm and observes the feedback from arms up to the selected arm. The learner’s goal is to find the arm that minimizes the expected total loss. The total loss is the sum of the cost incurred for selecting the arm and the stochastic loss associated with the selected arm. The problem is challenging because, without knowing the mean loss, one cannot compute the total loss for the selected arm. Clearly, learning is feasible only if the optimal arm can be inferred from the problem structure. As shown in the prior work, learning is possible when the problem instance satisfies the so-called ‘Weak Dominance’ (WD) property. Under WD, we show that our Thompson Sampling based algorithm for the USS problem achieves near optimal regret and has better numerical performance than existing algorithms.

While performing Feature Subset Selection (FSS) to identify important features, a weight is assigned to each feature that is not necessarily meaningful or interpretable w.r.t. final task and in turn leads to non-actionable information. To provide a solution to this problem of interpretable FSS, we introduce a novel notion of classification game with features as players and hinge loss based characteristic function. We use the Shapley value of this game to apportion the total training error to explicitly compute the contribution of each feature (Shapley Value based Error Apportioning, SVEA) to the total training error. We formalize the notion of interpret ability in FSS by identifying 3 final task related conditions. We empirically demonstrate that features with SVEA values less than zero are the dominant ones; this set is unique for a dataset as Shapley value is unique for a game instance. For the datasets that had negative apportioning, we observe a high value of the power of classification, PSV. It compares the performance of a set of linear and non-linear classifiers learned on Shapley value-based important features and the full feature set, in most of the cases. We customize a known Monte Carlo based approximation algorithm to avoid expensive Shapley value computations. We demonstrate the sample bias robustness of SVEA scheme by providing interval estimates. We illustrate all the above aspects on both synthetic and real datasets and showed that our scheme out-performs many existing approaches like recursive feature elimination and ReliefF in most of the cases.

PAC-Bayesian set up involves a stochastic classifier characterized by a posterior distribution on a classifier set, offers a high probability bound on its averaged true risk and is robust to the training sample used. For a given posterior, this bound captures the trade off between averaged empirical risk and KL-divergence based model complexity term. Our goal is to identify an optimal posterior with the least PAC-Bayesian bound. We consider a finite classifier set and 5 distance functions: KL-divergence, its Pinsker’s and a sixth degree polynomial approximations; linear and squared distances. Linear distance based model results in a convex optimization problem and we obtain a closed form expression for its optimal posterior. For uniform prior, this posterior has full support with weights negative-exponentially proportional to number of misclassifications. Squared distance and Pinsker’s approximation bounds are possibly quasi-convex and are observed to have single local minimum. We derive fixed point equations (FPEs) using partial KKT system with strict positivity constraints. This obviates the combinatorial search for subset support of the optimal posterior. For uniform prior, exponential search on a full-dimensional simplex can be limited to an ordered subset of classifiers with increasing empirical risk values. These FPEs converge rapidly to a stationary point, even for a large classifier set when a solver fails. We apply these approaches to SVMs generated using a finite set of SVM regularization parameter values on 9 UCI datasets. The resulting optimal posteriors (on the set of regularization parameters) yield stochastic SVM classifiers with tight bounds. KL-divergence based bound is the tightest, but is computationally expensive due to its non-convex nature and multiple calls to a root finding algorithm. Optimal posteriors for all 5 distance functions have lowest 10% test error values on most datasets, with that of linear distance being the easiest to obtain.

When agents compete for common resource and when the utilities derived by them, upon allocation, are independent across the agents and time slots, an opportunistic scheduler is used. The instantaneous utility of one agent can be low, however few among many would have `good' utility with high probability. Opportunistic schedulers utilize these opportunities, allocate resource at any time to a `good' agent. Efficient schedulers maximize the sum of accumulated utilities. Thus, every time `best' agent is allocated. This can result in negligible (unfair) accumulations for some agents, whose instantaneous utilities are `low' with high probability. Fair opportunistic schedulers are thus introduced (e.g., alpha-fair schedulers). We study their price of fairness (PoF). We group the agents into finite classes, each class having identical utilities and QoS requirements. We study the asymptotic PoF as agents increase, while maintaining class-wise proportions constant. Asymptotic PoF is less than one, depends only upon the differences in the largest utilities of individual classes and is less than the maximum such normalized differences. The PoF is zero initially and increases with increase in fairness requirements to an upper bound strictly less than one. We observe that the fair schedulers are essentially priority schedulers, which facilitated easy analysis of PoF.

Conservation laws and the related achievable region for mean waiting times are important concepts in multi-class queues. The nice geometric polytope structure of this region driven by the conservation law is exploited extensively for dynamic control of multi-class queues. Such control problems have wide range of applications in computers, communication networks and manufacturing systems. Tail probability of each class's waiting time is another important performance measure in any multi-class queue. This paper studies an approximate conservation law, the related achievable region and completeness of the tail probability of waiting time of each class in two class M/G/1 queues. We use completeness of the recently introduced relative priority scheme for mean waiting time vector as well as a suitable partition of the stability region of the queue to show that this approximate achievable region for tail probabilities is enclosed in a trapezium. We also study the tightness of bounds based on this decomposition of the stability region.

Completeness of some scheduling policies with mean waiting time performance measure is used quiet extensively in literature for dynamic control of multi-class queues due to its wide range of applications in computers, communication networks and manufacturing systems. For a single class queue, we introduce the idea of 2-moment completeness of a parametrized class of policies that also have to be non pre-emptive, non anticipative and work conserving. Significance of this idea lies in the importance of variance (or second moment) of waiting time in any queuing system. Some parametrized classes of policies are identified and shown to be 2-moment complete for M/M/1 queues. Some well known queue disciplines viz random order of service (ROS), Random Assigned Priority (RAP), etc., turn out to be 2-moment incomplete. We introduce a parametrized priority scheme that also turns out to be 2-moment incomplete. Further, few preemptive and anticipative scheduling disciplines are shown to have second moment beyond the achievable region of non pre-emptive, non anticipative and work conserving scheduling policies. Some optimal control problems are discussed to illustrate the possible applications of 2-moment complete parametrized set of policies.

Delay Tolerant Networks (DTNs) have gained importance in the recent past, as cost-effective alternative, in scenarios where delays can be accommodated. They work well in discretely connected network, where there is no direct connectivity between some/all components of the system. But the mobility of nodes creates occasional contact opportunities. The randomly moving nodes cooperate to help a fixed source, in delivering message to a far away destination within the given time threshold. The objective is to optimize the delivery success probability, which turns out to be a risk sensitive cost. The success probability depends upon the contact rates, which in turn depend upon the power used by the nodes to remain visible. The more the power used by a node, the larger is the radius for which it is visible. However these nodes are power constrained. This leads to a constrained finite horizon, Risk sensitive Markov Decision Process (MDP). In this paper we propose a linear program (LP) based approach to solve the corresponding dynamic programming equations. This approach enables us in handling the constraints. We showed using numerical simulations that, given a hard power constraint, the solution of the constrained MDP performs significantly superior in comparison with a solution obtained by optimizing a joint cost.

Many device to device communication networks can be modelled by multi-class tandem queues. In many applications, it is desired to have different quality of service for various classes. This can be achieved by implementing dynamic priority across classes. Performance analysis is an important aspect in such multi-class tandem queueing models for resource allocation. In this paper, we analyse two important, relatively complex and analytically intractable performance measures, tail probability and switching frequency, for two class queueing system with two different (relative and earliest due date based) dynamic priority schemes across classes. Such a two class queueing system can be used to model voice and data calls in communication networks. A simulator is built to analyse such queueing systems and various observations are made. Based on computational evidence, it is conjectured that two stage exponential queueing network with two classes of customers is decomposable as far as mean waiting times are concerned when relative priority is used across classes to schedule the customers. Based on further experiments, it is conjectured that departure processes with relative dynamic priority are indeed Poisson in two class exponential queue. We also conduct relevant statistical analysis in support of the conjectures.

We present two efficient discrete parameter simulation optimization (DPSO) algorithms for the long-run average cost objective. One of these algorithms uses the smoothed functional approximation (SFA) procedure, while the other is based on simultaneous perturbation stochastic approximation (SPSA). The use of SFA for DPSO had not been proposed previously in the literature. Further, both algorithms adopt an interesting technique of random projections that we present here for the first time. We give a proof of convergence of our algorithms. Next, we present detailed numerical experiments on a problem of admission control with dependent service times. We consider two different settings involving parameter sets that have moderate and large sizes, respectively. On the first setting, we also show performance comparisons with the well-studied optimal computing budget allocation (OCBA) algorithm and also the equal allocation algorithm.

DiffServ is an attractive candidate for providing relative QoS in the Internet. This is also easily amenable to simple and effective pricing mechanisms. By pricing access to a relative QoS, we can model a DiffServ node as a "join minimum cost queue" in which an arriving customer (packet or connection) determines the relative cost as a function of the congestion in the different queues and their access prices and decides to take service from that queue for which the cost is minimum. The Paris Metro pricing system and its work conserving variant called Tirupati pricing are analyzed in the presence of multiclass traffic and for static pricing. Two of the more interesting observations are that the disutility and revenue rate are not monotonic or convex functions of price and the revenue rate is very sensitive to the behavior of the delay sensitive class.