Testing indexability and computing Whittle and Gittins index in subcubic time

DOI10.1007/s00186-023-00821-4zbMath1527.90085arXiv2203.05207MaRDI QIDQ6107877

Nicolas Gast, Bruno Gaujal, Kimang Khun

Publication date: 28 June 2023

Published in: Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2203.05207

zbMATH Keywords

Markov decision processGittins indexmulti-armed banditWhittle indexfast matrix multiplicationrestless banditSherman-Morrison

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Stochastic scheduling theory in operations research (90B36) Markov and semi-Markov decision processes (90C40)

Related Items (1)

Exponential asymptotic optimality of Whittle index policy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges
• Asymptotically optimal priority policies for indexable and nonindexable restless bandits
• Asymptotically optimal index policies for an abandonment queue with convex holding cost
• Dynamic priority allocation via restless bandit marginal productivity indices
• A generalized Gittins index for a Markov chain and its recursive calculation
• Whittle's index policy for a multi-class queueing system with convex holding costs
• Whittle indexability in egalitarian processor sharing systems
• Whittle index based Q-learning for restless bandits with average reward
• On the Gittins index in the M/G/1 queue
• Gaussian elimination is not optimal
• On the computation of Whittle's index for Markovian restless bandits
• ON THE OPTIMALITY OF AN INDEX RULE IN MULTICHANNEL ALLOCATION FOR SINGLE-HOP MOBILE NETWORKS WITH MULTIPLE SERVICE CLASSES
• A (2/3)n³ Fast-Pivoting Algorithm for the Gittins Index and Optimal Stopping of a Markov Chain
• Index Policies for the Admission Control and Routing of Impatient Customers to Heterogeneous Service Stations
• PROPERTIES OF THE GITTINS INDEX WITH APPLICATION TO OPTIMAL SCHEDULING
• Linear Programming for Finite State Multi-Armed Bandit Problems
• The Multi-Armed Bandit Problem: Decomposition and Computation
• On an index policy for restless bandits
• The Functional Equations of Undiscounted Markov Renewal Programming
• An index policy for a stochastic scheduling model with improving/deteriorating jobs
• Indexability and Index Heuristics for a Simple Class of Inventory Routing Problems
• Indexability of Restless Bandit Problems and Optimality of Whittle Index for Dynamic Multichannel Access
• Some indexable families of restless bandit problems

This page was built for publication: Testing indexability and computing Whittle and Gittins index in subcubic time