4.8k citations · 5.1k across the 59 of their papers we have counts for
10 papers · 1 filter
LP Based Upper and Lower Bounds for Cesàro and Abel Limits of the Optimal Values in Problems of Control of Stochastic Discrete Time Systems
Konstantin Avrachenkov, Vladimir Gaitsgory, Lucas Gamertsfelder
In this paper, we study asymptotic properties of problems of control of stochastic discrete time systems (also known as Markov decision processes) with time averaging and time disc…
LFGCN: Levitating over Graphs with Levy Flights
Yuzhou Chen, Yulia R. Gel, Konstantin Avrachenkov
Due to high utility in many applications, from social networks to blockchain to power grids, deep learning on non-Euclidean objects such as graphs and manifolds, coined Geometric D…
Higher-Order Spectral Clustering for Geometric Graphs
Konstantin Avrachenkov, Andrei Bobu, Maximilien Dreveton
The present paper is devoted to clustering geometric graphs. While the standard spectral clustering is often not effective for geometric graphs, we present an effective generalizat…
Online Algorithms for Estimating Change Rates of Web Pages
Konstantin Avrachenkov, Kishor Patil, Gugan Thoppe
A search engine maintains local copies of different web pages to provide quick search results. This local cache is kept up-to-date by a web crawler that frequently visits these dif…
Community recovery in non-binary and temporal stochastic block models
Konstantin Avrachenkov, Maximilien Dreveton, Lasse Leskelä
This article studies the estimation of latent community memberships from pairwise interactions in a network of nodes, where the observed interactions can be of arbitrary type,…
Red Light Green Light Method for Solving Large Markov Chains
Konstantin Avrachenkov, Patrick Brown, Nelly Litvak
Discrete-time discrete-state finite Markov chains are versatile mathematical models for a wide range of real-life stochastic processes. One of most common tasks in studies of Marko…
Almost exact recovery in noisy semi-supervised learning
Konstantin Avrachenkov, Maximilien Dreveton
Graph-based semi-supervised learning methods combine the graph structure and labeled data to classify unlabeled data. In this work, we study the effect of a noisy oracle on classif…
Dynamic social learning under graph constraints
Konstantin Avrachenkov, Vivek S. Borkar, Sharayu Moharir +1
We introduce a model of graph-constrained dynamic choice with reinforcement modeled by positively -homogeneous rewards. We show that its empirical process, which can be written…
Change Rate Estimation and Optimal Freshness in Web Page Crawling
Konstantin Avrachenkov, Kishor Patil, Gugan Thoppe
For providing quick and accurate results, a search engine maintains a local snapshot of the entire web. And, to keep this local cache fresh, it employs a crawler for tracking chang…
Whittle index based Q-learning for restless bandits with average reward
Konstantin E. Avrachenkov, Vivek S. Borkar
A novel reinforcement learning algorithm is introduced for multiarmed restless bandits with average reward, using the paradigms of Q-learning and Whittle index. Specifically, we le…