Computational Complexity of Adaptive Algorithms

Author(s)

da Cunha Rodrigues, Elisangela Silva ; Rodrigues, Fabricio Augusto ; de Azevedo da Rocha, Ricardo Luis ; Chang, T

• Document type: Journal article
• Source: 2012 THIRD INTERNATIONAL CONFERENCE ON THEORETICAL AND MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE (ICTMF 2012); v. 38, p. 6-pg., 2013-01-01.

Abstract

The aim is to discuss the computational complexity of algorithmic solutions based on adaptive approaches, by means of an Adaptive Maximum Entropy algorithm. The idea behind this choice is to define a case study under a more general model of making any algorithm adaptive. The main premise herein is that traditional adaptive approaches uses a greedy approximation of the solution, in such a way that adaptive actions are used, to comprise a heuristic search or cut on the search space. One of the results of the paper shows that an adaptive solution can have up to O(2(m)) x O(e(m)) alternatives in the search space, which is far larger than traditional approaches, and yet the search is performed faster than with traditional approaches. (AU)

• FAPESP's process: 11/17096-5 - Use of adaptive techniques in reinforcement learning
• Grantee: Ricardo Luis de Azevedo da Rocha
• Support Opportunities: Scholarships abroad - Research