We consider the problem of learning stable matchings with unknown preferences in a decentralized and uncoordinated manner, where ``decentralized" means that players make decisions individually without the influence of a central platform, and ``uncoordinated" means that players do not need to synchronize their decisions using pre-specified rules. First, we provide a game formulation for this problem with known preferences, where the set of pure Nash equilibria (NE) coincides with the set of stable matchings, and mixed NE can be rounded to a stable matching. Then, we show that for hierarchical markets, applying the exponential weight (EXP) learning algorithm to the stable matching game achieves logarithmic regret in a fully decentralized and uncoordinated fashion. Moreover, we show that EXP converges locally and exponentially fast to a stable matching in general matching markets. We complement our results by introducing another decentralized and uncoordinated learning algorithm that globally converges to a stable matching with arbitrarily high probability.

The continuous nature of belief states in POMDPs presents significant computational challenges in learning the optimal policy. In this paper, we consider an approach that solves a Partially Observable Reinforcement Learning (PORL) problem by approximating the corresponding POMDP model into a finite-state Markov Decision Process (MDP) (called Superstate MDP). We first derive theoretical guarantees that improve upon prior work that relate the optimal value function of the transformed Superstate MDP to the optimal value function of the original POMDP. Next, we propose a policy-based learning approach with linear function approximation to learn the optimal policy for the Superstate MDP. Consequently, our approach shows that a POMDP can be approximately solved using TD-learning followed by Policy Optimization by treating it as an MDP, where the MDP state corresponds to a finite history. We show that the approximation error decreases exponentially with the length of this history. To the best of our knowledge, our finite-time bounds are the first to explicitly quantify the error introduced when applying standard TD learning to a setting where the true dynamics are not Markovian.

We consider a communication system consisting of a server that tracks and publishes updates about a time-varying data source or event, and a gossip network of users interested in closely tracking the event. The timeliness of the information is measured through the version age of information. The users wish to have their expected version ages remain below a threshold, and have the option to either rely on gossip from their neighbors or subscribe to the server directly to follow updates about the event if the former option does not meet the timeliness requirements. The server wishes to maximize its profit by increasing the number of subscribers and reducing costs associated with the frequent sampling of the event. We model the problem setup as a Stackelberg game between the server and the users, where the server commits to a frequency of sampling the event, and the users make decisions on whether to subscribe or not. As an initial work, we focus on directed networks with unidirectional flow of information and obtain the optimal equilibrium strategies for all the players. We provide simulation results to confirm the theoretical findings and provide additional insights.

The performance of Transfer Learning (TL) significantly depends on effective pretraining, which not only requires extensive amounts of data but also substantial computational resources. As a result, in practice, it is challenging to successfully perform TL at the level of individual model developers. Federated Learning (FL) addresses these challenges by enabling collaboration among individual clients through an indirect expansion of the available dataset, distribution of the computation burden across different entities, and privacy-preserving communication mechanisms. Despite several attempts to devise effective transferable FL approaches, several important issues remain unsolved. First, existing methods in this setting primarily focus on optimizing transferability within their local client domains, thereby ignoring transferability over the global learning domain. Second, most approaches focus on analyzing indirect transferability metrics, which does not allow for accurate assessment of the final target loss and extent of transferability. To address these issues, we introduce two important FL features into the model. The first boosts transferability via an exchange protocol between the clients and the server that includes information about cross-client Jacobian (gradient) norms. The second feature promotes an increase of the average of the Jacobians of the clients at the server side, which is subsequently used as a local regularizer that reduces the cross-client Jacobian variance. A rigorous analysis of our transferable federated algorithm, termed FedGTST (Federated Global Transferability via Statistics Tuning), reveals that increasing the averaged Jacobian norm across clients and reducing its variance ensures tight control of the target loss. This insight leads to the first known upper bound on the target loss of transferable federated learning in terms of the source loss and source-target domain discrepancy. Extensive experimental results on datasets including MNIST → MNIST-M and CIFAR10 → SVHN suggest that FedGTST significantly outperforms other relevant baselines, such as FedSR. For example, on the second source-target dataset pair, we improve the accuracy of FedSR by 9.8% and that of FedIIR by 7.6% when the backbone used is LeNet.

We consider the problem of allocating multiple indivisible items (resources) to a set of capacitated agents to maximize the social welfare subject to network effects (externalities). Here, the social welfare is given by the sum of agents' utilities and externalities capture the effect that one user of an item has on the item's value to others. We first provide a general formulation that captures some of the existing single-item or multi-item resource allocation models as a special case and analyze it under various settings of positive/negative externality weights and convex/concave externality functions. In our formulation, the externality weights capture whether the agents are influenced positively or negatively by those who receive the same item, and the convex/concave externality functions determine the growth rate of network effects for different pairs of items and agents. We then show that the maximum social welfare (MSW) problem benefits some nice diminishing or increasing marginal return properties, hence making a connection to submodular/supermodular optimization. That allows us to devise various polynomial-time approximation algorithms using the Lovaśz and multilinear extensions of the objective functions. More specifically:

Motivated by applications in web caches and content delivery in peer-to-peer networks, we consider the non-metric data placement problem and develop distributed algorithms for computing or approximating its optimal solutions. In this problem, the goal is to store copies of the data points among a set of cache-capacitated servers to minimize overall data storage and clients' access costs. We first show that the non-metric data placement problem is inapproximable up to a logarithmic factor. We then provide a game-theoretic decomposition of the objective function and show that a natural type of Glauber dynamics in which servers update their cache contents with probability proportional to the utility they receive from caching those data will converge to an optimal global solution for a sufficiently large noise parameter. In particular, we establish the polynomial mixing time of the Glauber dynamics for a certain range of noise parameters. Such a game-theoretic decomposition not only provides a good performance guarantee in terms of content delivery but also allows the system to operate in a fully distributed manner, hence reducing its computational load and improving its robustness to failures. Moreover, we provide another auction-based distributed algorithm, which allows us to approximate the optimal solution with a performance guarantee that depends on the ratio of the revenue vs. social welfare obtained from the underlying auction.

We consider information dissemination over a network of gossiping agents (nodes). In this model, a source keeps the most up-to-date information about a time-varying binary state of the world, and n receiver nodes want to follow the information at the source as accurately as possible. When the information at the source changes, the source first sends updates to a subset of m≤n nodes. After that, the nodes share their local information during the gossiping period to disseminate the information further. The nodes then estimate the information at the source using the majority rule at the end of the gossiping period. To analyze information dissemination, we introduce a new error metric to find the average percentage of nodes that can accurately obtain the most up-to-date information at the source. We characterize the equations necessary to obtain the steady-state distribution for the average error. Through numerical results, we first show that when the source’s transmission capacity m is limited, gossiping can be harmful as it causes incorrect information to disseminate. We then find the optimal gossip rates to minimize the average error for a fixed m.

We consider an online assortment problem with $[n]=\{1,2,\ldots,n\}$ sellers, each holding exactly one item $i\in[n]$ with initial inventory $c_i\in \mathbb{Z}_+$, and a sequence of homogeneous buyers arriving over a finite time horizon $t=1,2,\ldots,m$. There is an online platform whose goal is to offer a subset $S_t\subseteq [n]$ of sellers to the arriving buyer at time $t$ to maximize the expected revenue derived over the entire horizon while respecting the inventory constraints. Given an assortment $S_t$ at time $t$, it is assumed that the buyer will select an item from $S_t$ based on the well-known multinomial logit model, a well-justified choice model from the economic literature. In this model, the revenue obtained from selling an item $i$ at a given time $t$ critically depends on the assortment $S_t$ offered at that time and is given by the Nash equilibrium of a Bertrand game among the sellers in $S_t$. This imposes a strong dependence/externality among the offered assortments, sellers' revenues, and inventory levels. Despite that challenge, we devise a constant competitive algorithm for the online assortment problem with homogeneous buyers. It answers a question in [Z. Zheng and R. Srikant, Optimal Search Segmentation Mechanisms for Online Platform Markets, preprint, arXiv:1908.07489, 2019] that considered the static version of the assortment problem with only one buyer and no inventory constraints. We also show that the online assortment problem with heterogeneous buyers does not admit a constant competitive algorithm. To compensate that issue, we then consider the assortment problem under an offline setting with heterogeneous buyers. Under a mild market consistency assumption, we show that the generalized Bertrand game admits a pure Nash equilibrium over general buyer-seller bipartite graphs. Finally, we develop an $O(\ln m)$-approximation algorithm for optimal market segmentation of the generalized Bertrand game which allows the platform to derive higher revenues by partitioning the market into smaller pools.

We consider a learning system based on the conventional multiplicative weight (MW) rule that combines experts' advice to predict a sequence of true outcomes. It is assumed that one of the experts is malicious and aims to impose the maximum loss on the system. The system's loss is naturally defined to be the aggregate absolute difference between the sequence of predicted outcomes and the true outcomes. We consider this problem under both offline and online settings. In the offline setting where the malicious expert must choose its entire sequence of decisions a priori, we show somewhat surprisingly that a simple greedy policy of always reporting false prediction is asymptotically optimal with an approximation ratio of 1+O√(ln N)/N, where N is the total number of prediction stages. In particular, we describe a policy that closely resembles the structure of the optimal offline policy. For the online setting where the malicious expert can adaptively make its decisions, we show that the optimal online policy can be efficiently computed by solving a dynamic program in O(N3). We also discuss a generalization of our model to multi-expert settings. Our results provide a new direction for vulnerability assessment of commonly-used learning algorithms to internal adversarial attacks.

Motivated by many real-world examples, such as recommendation systems or sensor fusion, and aiming to capture the influence of malicious experts who intentionally degrade the performance of learning systems, we analyze optimal adversarial strategies against the weighted average prediction algorithm in the learning with expert advice framework. All but one expert is honest and the malicious expert's goal is to sabotage the performance of the algorithm by strategically providing dishonest recommendations. We formulate the problem as a Markov decision process and analyze it under various settings. For the logarithmic loss, somewhat surprisingly, we prove that the optimal strategy for the adversary is the greedy policy, i.e., lying at every step. For the absolute loss, in the 2-experts, discounted cost setting, we prove that the optimal strategy is a threshold policy, where the malicious expert tells the truth until he earns enough weight and then lies afterwards. We extend the results to the infinite horizon problem and find the exact thresholds for the stationary optimal policy. Finally, we use a mean field approach in the N-experts setting to find the optimal strategy when the predictions of the honest experts are independent and identically distributed. We justify our results using simulations throughout this paper.

We consider a generalized model of learning from expert advice in which experts could abstain from participating at some rounds. Our proposed online algorithm falls into the class of weighted average predictors and uses a time-varying multiplicative weight update rule. This update rule changes the weight of an expert based on his or her relative performance compared to the average performance of available experts at the current round. This makes the algorithm suitable for recommendation systems in the presence of an adversary with many potential applications in the new emerging area of the Internet of Things. We prove the convergence of our algorithm to the best expert, defined in terms of both availability and accuracy, in the stochastic setting. In particular, we show the applicability of our definition of best expert through convergence analysis of another well-known algorithm in this setting. Finally, through simulation results on synthetic and real datasets, we justify the out-performance of our proposed algorithms compared to the existing ones in the literature.