NDLI: Characterization and computation of restless bandit marginal productivity indices

Please wait, while we are loading the content...

Power allocation game for fading MIMO multiple access channels with antenna correlation

Multiple access game in ad-hoc network

How to measure efficiency?

Speed and accuracy of network simulation in the SimGrid framework

NSOSS: the non-synchronized optical switch simulator

Enabling cross layer design: adding the MadWifi extensions to Nsclick

Decentralized control of large-scale networks as a game with local interactions: cross-layer TCP/IP optimization

Enhanced Skype traffic identification

A toolkit for performability evaluation based on stochastic UML state machines

Utility maximization for resolving throughput/reliability trade-offs in an unreliable network with multipath routing

Vector precoding in wireless communications: a replica symmetric analysis

Hybrid simulation of a FIFO queuing system with trace-driven background traffic

Aggregated bounding Markov processes applied to the analysis of tandem queues

Autonomic QoS-Aware resource management in grid computing using online performance models

Stationary delays for a two-class priority queue with impatient customers

Cellular network with continuum priority set

CyNC: a MATLAB/SimuLink toolbox for network calculus

Simulation versus analytic-numeric methods: illustrative examples

Random multi-access protocols in networks with partial interaction and non-saturated nodes: a mean field approach

Quantitative analysis of biochemical signalling pathways

Constrained Markov games with transition probabilities controlled by a single player

A policy iteration algorithm for Markov decision processes skip-free in one direction

A tool for the analysis of hierarchical service-oriented extended open fork/join queueing networks

On the properties of acyclic bilateral phase type distributions

Efficiency of random walks for search in different network structures

Split: a flexible and efficient algorithm to vector-descriptor product

Distributed subchannel assignment in a multiuser MIMO relay

The simplex game: can selfish users learn to operate efficiently in wireless networks?

Pricing under information asymmetry for a large population of users

Evaluating the goodness of MANETs performance results obtained with the ns-2 simulator

ns2-MIRACLE: a modular framework for multi-technology and cross-layer support in network simulator 2

User-level performance evaluation of VoIP using ns-2

Stackelberg approach for pricing differentiated services

Quantifying ILP by means of graph theory

Modeling and evaluation of supply chains with GSPN components

Asymmetric delay in evolutionary games

Cross-system resource allocation based on random matrix theory

Using parallel replications for sequential estimation of multiple steady state quantiles

A histogram-based stochastic process for finite buffer occupancy analysis

A productivity centered application performance tuning framework

Kernel density in the use of the strong stability method to evaluate the proximity of G/M/1 and M/M/1 systems

Maximum delay-constrained source rate over a wireless channel

End-to-end delay bounds in FIFO-multiplexing tandems

Detecting non-ergodic simulation models of logistics networks

Dynamic retransmission limit scheme for routing in multi-hop ad hoc networks

Characterization and computation of restless bandit marginal productivity indices

Computing an index policy for bandits with switching penalties

Can matrix-layout-independent numerical solvers be efficient?: implementing the Moebius state-level abstract functional interface for ZDDs

Approximating optimal load balancing policy in discriminatory processor sharing systems

Discrete time stochastic automata networks: using structural properties and stochastic bounds to simplify the SAN

Information theoretic aspects of fairness criteria in network resource allocation problems

End-to-end link power control in optical networks using Nash bargaining solution

A discrete-event simulation tool for the analysis of simultaneous events

Simulation of peer-to-peer streaming over large-scale networks using OPSS

SYNTONY: network protocol simulation based on standard-conform UML 2 models

Optimal cluster-head deployment in wireless sensor networks with redundant link requirements

Estimating Markov-modulated compound Poisson processes

Product form for stochastic automata networks

SEPCOM: customizable zero copy model

Detecting the duration of initial transient in steady state simulation of arbitrary performance measures

Approximate queueing network analysis of patient treatment times

Fast evaluation of the moments of the interval availability of large Markov models

Continuous PEPA queues: individual behaviour in continuous queueing networks

Joint uplink and downlink capacity considerations in admission control in multiservice CDMA/HSDPA systems

Optimal routing for end-to-end guarantees: the price of multiplexing

Perfect simulation and monotone stochastic bounds

Preliminary results on social learning with partial observations

A survey on distributed approaches to graph based reputation measures

A stackelberg game for power control and channel allocation in cognitive radio networks

Multiple equilibria in symmetric strategies for simultaneous auctions in next-generation bandwidth markets

Modeling the underwater acoustic channel in ns2

Cooperative and non-cooperative control for slotted aloha with random power level selections algorithms

An overview of long-range dependent network traffic engineering and analysis: characteristics, simulation, modelling and control

Representing LCFSPR BCMP service center with Coxian service time by GSPN

Level crossing ordering of Markov chains: computing end to end delays in an all optical network

The software architecture of the OsMoSys multisolution framework

Finite-buffer bulk service queue under Markovian service process

Distributed subchannel assignment in an OFDMA relay

Tool-based performance evaluation of the blackboard communication system

Experiences from the SSR development

Closed form solutions for water-filling problems in optimization and game frameworks

A binomial measure method for traffic modeling

The twin measure for queueing system predictability

Random walk based routing protocol for wireless sensor networks

Characterization and computation of restless bandit marginal productivity indices

Content Provider	ACM Digital Library
Author	Niño-Mora, José
Abstract	The restless bandit problem furnishes a powerful modeling paradigm for settings involving the optimal dynamic priority allocation to multiple stochatic projects, given as binary-action (active/passive) Markov decision processes (MDPs). Though generally intractable, Whittle (1988) introduced a tractable priority-index policy, which has been developed in recent work by the author in an extended framework based on the unifying concept of marginal productivity index (MPI). A growing body of empirical evidence shows MPI policies to be nearly optimal in diverse applications, which motivates the interest to compute efficiently the MPI. For such a purpose, we extend to restless bandits the parametric linear programming (LP) approach deployed in [J. Niño-Mora. A $(2/3)n^{3}$ fast-pivoting algorithm for the Gittins index and optimal stopping of a Markov chain, INFORMS J. Comp., in press] for classic (nonrestless) bandits. Yet the extension is not straightforward, as the MPI is only defined for the restricted range of so-called indexable bandits, which motivates the quest for methods to establish indexability. This paper furnishes algorithmic and analytical tools to realize the potential of MPI policies in large-scale applications, presenting the following contributions: (i) an algorithmic characterization of indexability, for which two block implementations are given; and (ii) new analytical conditions for indexability --- termed LP-indexability --- that leverage knowledge on the structure of optimal policies, under which the MPI is computed faster by the adaptive-greedy algorithm previously introduced by the author under more stringent (PCL-indexability) conditions, for which a new fast-pivoting block implementation is given. The paper further reports on a computational study, which measures the runtime performance of the algorithms and demonstrates the high prevalence of indexability and PCL-indexability.
Starting Page	1
Ending Page	10
Page Count	10
File Format	PDF
ISBN	9789639799004
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2007-10-22
Publisher Place	Brussels
Access Restriction	Subscribed
Subject Keyword	Index policies Markov decision processes Block algorithms Marginal productivity index Restless bandits
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in