Online learning algorithms have been successfully used to design caching policies with sublinear regret in the total number of requests, with no statistical assumption about the request sequence. Most existing algorithms involve computationally expensive operations and require knowledge of all past requests. However, this may not be feasible in practical scenarios such asfemtocaching, where a base station (BS) jointly decides the content of many edge caches and visibility of all requests at the BS requires constant communication between these caches and the BS. To capture this constraint, we study a single cache problem under a more restrictive setting, that we refer to as the Bernoulli Partial Observability (BPO) model, in which the caching policy only observes a request with probability$p$, reflecting the fraction of requests forwarded from the edge caches to the BS in thefemtocachingexample. We propose a policy, based on the classic online learning algorithm Follow-the-Perturbed-Leader (FPL), that achieves an asymptotically optimal regret bound of$\mathcal {O}(\sqrt {CT/p})$under BPO in$\mathcal {O}(1)$amortized time complexity as$T$goes to infinity, where$C$is the cache size and$T$is the number of requests. Moreover, we show that our policy extends to bipartite caching albeit with a sublinear$\alpha $-regret for$\alpha =1-1/e$and a higher computational cost. The experimental evaluation compares the proposed solution with classic caching policies and validates the proposed approach using both synthetic and real-world request traces.

The Kelly or proportional allocation mechanism is a simple and efficient auction-based decentralized resource allocation scheme that distributes an infinitely divisible resource proportionally to the agents' bids. When agents are aware of the allocation mechanism, their interactions form a game. The properties of its Nash equilibria are well understood under the simplifying assumption of unbounded budgets. In this paper, we analyze the game in a more realistic budget-constrained setting, motivated by its optimality in terms of the liquid price of anarchy (LPoA). Specifically, we establish a sufficient condition for the uniqueness of the Nash equilibrium and design a distributed sequential learning procedure that provably converges to the equilibrium. In particular, our sufficient condition holds when the payoff functions of the agents are of the proportional fair type in the allocated fraction. Finally, extensive numerical experiments shed light on the interplay between the heterogeneity of the payoff functions and the agents' budgets.

Similarity caching allows requests for an item$i$to be served by a similar item i’. Applications include recommendation systems, multimedia retrieval, and machine learning. Recently, many similarity caching policies have been proposed, but still we do not know how to compute the hit rate even for simple policies, like SIM-LRU and RND-LRU that are straightforward modifications of classic caching algorithms. This paper proposes the first algorithm to compute the hit rate of similarity caching policies under the independent reference model for the request process. In particular, we show how to extend the popular time-to-live approximation in classic caching to similarity caching. The algorithm is evaluated on both synthetic and real world traces.