Check out the recent ICML'2010 workshop on Budgeted Learning  see here.
Learning tasks typically begin with a data sample  eg, symptoms and test results for a set of patients, together with their clinical outcomes. By contrast, many realworld studies begin with no actual data, but instead with a budget  funds that can be used to collect the relevant information. For example, one study has allocated $30 thousand to develop a system to diagnose cancer, based on a battery of patient tests, each with its own (known) costs and (unknown) discriminative powers. Given our goal of identifying the most accurate classifier, what is the best way to spend the $30 thousand? Should we indiscriminately run every test on every patient, until exhausting the budget? Or, should we selectively, and dynamically, determine which tests to run on which patients? We call this task budgeted learning.
Our initial work on this task studied the theoretical foundations of budgeted learning and proved several important results, such as NPhardness. Our other work builds upon the theory, and provides algorithms for budgeted learning a passive (Naive Bayes) classifer. Finally, our most recent extensions consider both learning and classifying under a budget, and thus budgetedlearn a bounded active classifier. As budgeted learning is a sequential decision problem, we also provide empirical results which demonstrate that the obvious Reinforcement Learning techniques do not perform particularly well on this highdimensional and complex task, and are typically bested by our simpler, heuristic policies. A list of all these works and additional experiments is given below. (See also Open Problems.)
Title  Authors  Summary  Appears In  Links  

1  Active Model Selection  Omid Madani, Dan Lizotte, Russell Greiner  Explores the budgeted multiarmed bandit task.  UAI 2004  Details, or Paper 
2  Reinforcement Learning for Active Model Selection  Aloak Kapoor, Russell Greiner  Compares RL to heuristic spending policies.  UBDM 2005 (KDD Workshop)  Details, or Paper 
3  Budgeted Learning of NaiveBayes Classifiers  Dan Lizotte, Omid Madani, Russell Greiner  Provides effective algorithms for budgeted learning a passive classifier.  UAI 2003  Details, or Paper 
4  Learning and Classifying under Hard Budgets  Aloak Kapoor, Russell Greiner  Considers budgeted learning a bounded active classifier.  ECML 2005  Details, or Paper* 
5  Using Value of Information to Learn and Classify under Hard Budgets  Russell Greiner  Short abstract summarizing budgeted learning results, in context of ValueofInformation. 
VOI 2005
(NIPS Workshop) 
Paper 
6  Budgeted Learning of Naive Bayes Classifiers  Dan Lizotte  MSc dissertation Everything known about 1 and 3. 
Dissertation  
7  Learning and Classifying under Hard Budgets  Aloak Kapoor  MSc dissertation Everything known about 2 and 4. 
Dissertation  
8  Budgeted Distribution Learning in Parametric Models  Liuyang (Spike) Li Barnabas Poczos Csaba Szepesvári, Russell Greiner  Learning the parameters for belief net, to minimize expected KL divergence  ICML 2010

Paper 
9  Actively Learning Generative Model  Liuyang (Spike) Li  MSc dissertation Everything known about 8. 
Dissertation 
Active Model Selection 
Omid Madani, Dan Lizotte, Russell Greiner 
Short version (in UAI 2004) 
Longer version (Under revision; includes more explanations, experimental results as well as proofs and derivations in the appendices). 
Algorithm Animations

Budgeted Learning of Naive Bayes Classifiers 
Dan Lizotte, Omid Madani, Russell Greiner 
Full Paper (UAI 2003) 
Empirical Results

Learning and Classifying under Hard Budgets 
Aloak Kapoor, Russell Greiner 
Full Paper* (ECML 2005) 
(Extended version, with Proofs) 
Foundations: Learning CostSensitive Active Classifiers 
Reinforcement Learning for Active Model Selection 
Aloak Kapoor, Russell Greiner 
Full Paper
(Utility Based Data Mining Workshop, KDD 2005)
Note: * = copyright SpringerVerlag. Visit the publisher's website here 