Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/1900008.1900072acmconferencesArticle/Chapter ViewAbstractPublication Pagesacm-seConference Proceedingsconference-collections
research-article

Generating three binary addition algorithms using reinforcement programming

Published: 15 April 2010 Publication History

Abstract

Reinforcement Programming (RP) is a new technique for automatically generating a computer program using reinforcement learning methods. This paper describes how RP learned to generate code for three binary addition problems: simulate a full adder circuit, increment a binary number, and add two binary numbers. Each problem is presented as an extension of the one previous to it, which provides an introduction to the practical application of RP. Each solution uses a dynamic, episodic form of delayed Q-Learning algorithm. "Dynamic" means that grows the policy during learning, and prunes it before the policy is translated to source code. This is different from Q-Learning models that use fixed-size tables or neural net function approximators to store q-values associated with (state, action) pairs. The states, actions, rewards, other parameters, and results of experiments are presented for each of the three problems.

References

[1]
T. Jaakkola, S. P. Singh, and M. I. Jordan. Reinforcement learning algorithm for partially observable Markov decision problems. In G. Tesauro, D. Touretzky, and T. Leen, editors, Advances in Neural Information Processing Systems, volume 7, pages 345--352. The MIT Press, 1995.
[2]
K. E. Kinnear. Evolving a Sort: Lessons in Genetic Programming. In Proceedings of the 1993 International Conference on Neural Networks, volume 2, pages 881--888. IEEE Press, 1993.
[3]
J. R. Koza. Genetic Programming IV: Routine Human-Competitive Machine Intelligence. Kluwer Academic Publishers, 2003.
[4]
T. M. Mitchell. Machine Learning. McGraw-Hill, New York, 1997.
[5]
R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, 1998.
[6]
C. J. Watkins. Learning from delayed rewards. PhD thesis, Cambridge university, 1989.
[7]
S. K. White. Reinforcement programming: A new technique in automatic algorithm development. Master's thesis, Brigham Young University, 2006.

Cited By

View all

Index Terms

  1. Generating three binary addition algorithms using reinforcement programming

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ACMSE '10: Proceedings of the 48th annual ACM Southeast Conference
    April 2010
    488 pages
    ISBN:9781450300643
    DOI:10.1145/1900008
    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

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 15 April 2010

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. automatic program generation
    2. binary addition
    3. reinforcement learning

    Qualifiers

    • Research-article

    Conference

    ACM SE '10
    Sponsor:
    ACM SE '10: ACM Southeast Regional Conference
    April 15 - 17, 2010
    Mississippi, Oxford

    Acceptance Rates

    ACMSE '10 Paper Acceptance Rate 48 of 94 submissions, 51%;
    Overall Acceptance Rate 502 of 1,023 submissions, 49%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 25 Nov 2024

    Other Metrics

    Citations

    Cited By

    View all

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media