RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación
Capítulo o parte de un libro (BookPart)
Stochastic tasks: difficulty and Levin search
We establish a setting for asynchronous stochastic tasks that
account for episodes, rewards and responses, and, most especially, the
computational complexity of the algorithm behind an agent solving a
task. This is used to determine the difficulty of a task as the (logarithm
of the) number of computational steps required to acquire an acceptable
policy for the task, which includes the exploration of policies and their
verification. We also analyse instance difficulty, task compositions and
decompositions., This work has been partially supported by the EU (FEDER) and the Spanish MINECO under grants TIN 2010-21062-C02-02, PCIN-2013-037 and TIN 2013-45732-C4-1-P, and by Generalitat Valenciana PROMETEOII 2015/013.