Approximation algorithms for budgeted learning problems

MaRDI QIDQ3549602zbMATH OpenFDO

Authors Sudipto Guha, Kamesh Munagala

Publication date 5 January 2009

zbMATH Keywords

approximation algorithmsbudgeted learning problemsbudgeted multi-armed bandit problemlinear programstochastic packing

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Recommendations

• The ratio index for budgeted learning, with applications
• Bandits with knapsacks
• Improvements and generalizations of stochastic knapsack and multi-armed bandit approximation algorithms: extended abstract
• Learning Theory
• Asymptotically optimal algorithms for budgeted multiple play bandits

Cited in

(27)

• A PAC algorithm in relative precision for bandit problem with costly sampling
• Asymptotically optimal algorithms for budgeted multiple play bandits
• Approximation and learning by greedy algorithms
• Approximation algorithms for stochastic combinatorial optimization problems
• Submodular stochastic probing on matroids
• Differentially private and budget-limited bandit learning over matroids
• Bayesian Incentive-Compatible Bandit Exploration
• Bandits with knapsacks
• Budgeted multi-armed bandit in continuous action space
• The ratio index for budgeted learning, with applications
• Learning Theory
• Stochastic unsplittable flows
• Optimal online contention resolution schemes via ex-ante prophet inequalities
• Stochastic graph exploration
• Bandits with global convex constraints and objective
• Improvements and generalizations of stochastic knapsack and Markovian bandits approximation algorithms
• Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
• Sensor scheduling for space object tracking and collision alert
• Asymptotically optimal multi-armed bandit policies under a cost constraint
• Per-round knapsack-constrained linear submodular bandits
• Improvements and generalizations of stochastic knapsack and multi-armed bandit approximation algorithms: extended abstract
• Efficient learning with partially observed attributes
• scientific article; zbMATH DE number 7053373 (Why is no real title available?)
• scientific article; zbMATH DE number 7650116 (Why is no real title available?)
• Stochastic graph exploration with limited resources
• Thompson sampling-based recursive block elimination for dynamic assignment under limited budget in pure-exploration
• Identifying approximate minimizers under stochastic uncertainity

This page was built for publication: Approximation algorithms for budgeted learning problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3549602)