Article

Analyzing feature generation for value-function approximation

Authors:

Christopher Painter-Wakefield,

Michael LittmanAuthors Info & Claims

ICML '07: Proceedings of the 24th international conference on Machine learning

Pages 737 - 744

https://doi.org/10.1145/1273496.1273589

Published: 20 June 2007 Publication History

Abstract

We analyze a simple, Bellman-error-based approach to generating basis functions for value-function approximation. We show that it generates orthogonal basis functions that provably tighten approximation error bounds. We also illustrate the use of this approach in the presence of noise on some sample problems.

References

[1]

Atkeson, C. G., Moore, A. W., & Schaal, S. (1997). Locally weighted learning. Artificial Intelligence Review, 11, 11--73.

Digital Library

[2]

Boyan, J. A., & Moore, A. W. (1995). Generalization in reinforcement learning: Safely approximating the value function. Advances in Neural Information Processing Systems 7 (pp. 369--376). Cambridge, MA: The MIT Press.

[3]

Bradtke, S., & Barto, A. (1996). Linear least-squares algorithms for temporal difference learning. Machine Learning, 2, 33--58.

Digital Library

[4]

Freund, Y., & Schapire, R. (1995). A decision-theoretic generalization of on-line learning and an application to boosting. Proc. of the Second European Conference on Computational Learning Theory. LNCS.

Digital Library

[5]

Keller, P., Mannor, S., & Precup, D. (2006). Automatic basis function construction for approximate dynamic programming and reinforcement learning. Proceedings of the Twenty-third International Conference on Machine Learning.

Digital Library

[6]

Koller, D., & Parr, R. (1999). Computing factored value functions for policies in structured MDPs. Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI-99) (pp. 1332--1339). Morgan Kaufmann.

Digital Library

[7]

Lagoudakis, M., & Parr, R. (2003). Least squares policy iteration. Journal of Machine Learning Research, 4, 1107--1149.

Digital Library

[8]

Mahadevan, S., & Maggioni, M. (2006). Proto-value functions: A Laplacian framework for learning representation and control in Markov decision processes (Technical Report 2006--35). University of Massachusetts, Amherst.

[9]

Mallat, S. G., & Zhang, Z. (1993). Matching pursuits with time-frequency dictionaries. IEEE Transactions on Signal Processing, 41.

Digital Library

[10]

Menache, I., Mannor, S., & Shimkin, N. (2005). Basis function adaptation in temporal difference reinforcement learning. Annals of Operations Research, 134.

[11]

Munos, R. (2003). Error bounds for approximate policy iteration. Proceedings of the Twentieth International Conference on Machine Learning.

[12]

Sutton, R. S. (1988). Learning to predict by the methods of temporal differences. Machine Learning, 3, 9--44.

[13]

Van Roy, B. (1998). Learning and value function approximation in complex decision processes. Doctoral dissertation, Massachusetts Institute of Technology.

Digital Library

[14]

Vapnik, V., Golowich, S., & Smola, A. (1997). Support vector method for function approximation, regression estimation, and signal processing. Advances in Neural Information Processing Systems 9 (pp. 281--287). Cambridge, MA: MIT Press.

[15]

Yu, H., & Bertsekas, D. (2006). Convergence results for some temporal difference methods based on least squares (Technical Report LIDS-2697). Laboratory for Information and Decision Systems, Massachusetts Institute of Technology.

Cited By

Bozkus TMitra U(2024)Leveraging Digital Cousins for Ensemble Q-Learning in Large-Scale Wireless NetworksIEEE Transactions on Signal Processing10.1109/TSP.2024.336643472(1114-1129)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3366434
Wang HMiahi EWhite MMachado MAbbas ZKumaraswamy RLiu VWhite A(2024)Investigating the Properties of Neural Network Representations in Reinforcement LearningArtificial Intelligence10.1016/j.artint.2024.104100(104100)Online publication date: Mar-2024
https://doi.org/10.1016/j.artint.2024.104100
Chandak YThakoor SGuo ZTang YMunos RDabney WBorsa DKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Representations and exploration for deep reinforcement learning using singular value decompositionProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618568(4009-4034)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3618568
Show More Cited By

Analyzing feature generation for value-function approximation
1. Computing methodologies

Recommendations

Learning and value function approximation in complex decision processes
Some properties of a hypergeometric function which appear in an approximation problem

In this paper we consider properties and power expressions of the functions $$f:(-1,1)\rightarrow \mathbb{R }$$ and $$f_L:(-1,1)\rightarrow \mathbb{R }$$ , defined by $$\begin{aligned} f(x;\gamma )=\frac{1}{\pi }\int \limits _{-1}^1 \frac{(1+xt)^\gamma }{\sqrt{1-t^2}}\,\mathrm{d}t \quad \text{ and}\quad f_L(x;\gamma )=\frac{...
Value function approximation in reinforcement learning using the fourier basis
AAAI'11: Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence

We describe the Fourier basis, a linear value function approximation scheme based on the Fourier series. We empirically demonstrate that it performs well compared to radial basis functions and the polynomial basis, the two most popular fixed bases for ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICML '07: Proceedings of the 24th international conference on Machine learning

June 2007

1233 pages

ISBN:9781595937933

DOI:10.1145/1273496

Editor:
Zoubin Ghahramani
University of Cambridge, United Kingdom

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Machine Learning Journal

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICML '07 & ILP '07

Sponsor:

ICML '07 & ILP '07: The 24th Annual International Conference on Machine Learning held in conjunction with the 2007 International Conference on Inductive Logic Programming

June 20 - 24, 2007

Oregon, Corvalis, USA

Acceptance Rates

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

71
Total Citations
View Citations
444
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)3

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bozkus TMitra U(2024)Leveraging Digital Cousins for Ensemble Q-Learning in Large-Scale Wireless NetworksIEEE Transactions on Signal Processing10.1109/TSP.2024.336643472(1114-1129)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3366434
Wang HMiahi EWhite MMachado MAbbas ZKumaraswamy RLiu VWhite A(2024)Investigating the Properties of Neural Network Representations in Reinforcement LearningArtificial Intelligence10.1016/j.artint.2024.104100(104100)Online publication date: Mar-2024
https://doi.org/10.1016/j.artint.2024.104100
Chandak YThakoor SGuo ZTang YMunos RDabney WBorsa DKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Representations and exploration for deep reinforcement learning using singular value decompositionProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618568(4009-4034)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3618568
Bozkus TMitra U(2023)Link Analysis for Solving Multiple-Access MDPs With Large State SpacesIEEE Transactions on Signal Processing10.1109/TSP.2023.326056271(947-962)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TSP.2023.3260562
Ren JZeng YZhou SZhang Y(2021)An Experimental Study on State Representation Extraction for Vision-Based Deep Reinforcement LearningApplied Sciences10.3390/app11211033711:21(10337)Online publication date: 3-Nov-2021
https://doi.org/10.3390/app112110337
Oliehoek FWitwicki SKaelbling L(2021)A Sufficient Statistic for Influence in Structured Multiagent EnvironmentsJournal of Artificial Intelligence Research10.1613/jair.1.1213670(789-870)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1613/jair.1.12136
Ni CZhang ADuan YWang M(2021)Learning Good State and Action Representations via Tensor Decomposition2021 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT45174.2021.9518158(1682-1687)Online publication date: 12-Jul-2021
https://doi.org/10.1109/ISIT45174.2021.9518158
Field DAmmouche YPeña JJérusalem A(2021)Machine learning based multiscale calibration of mesoscopic constitutive models for composite materials: application to brain white matterComputational Mechanics10.1007/s00466-021-02009-1Online publication date: 28-Apr-2021
https://doi.org/10.1007/s00466-021-02009-1
Ghosh DBellemare MDaumé HSingh A(2020)Representations for stable off-policy reinforcement learningProceedings of the 37th International Conference on Machine Learning10.5555/3524938.3525271(3556-3565)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.5555/3524938.3525271
Ghasemi MHashemi AVikalo HTopcu U(2020)Identifying Sparse Low-Dimensional Structures in Markov Chains: A Nonnegative Matrix Factorization Approach2020 American Control Conference (ACC)10.23919/ACC45564.2020.9147586(1093-1098)Online publication date: Jul-2020
https://doi.org/10.23919/ACC45564.2020.9147586
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents