Projects

Phase 2 Projects

Value Representation in Large Factored State Spaces


Project leaders: Klaus Obermayer (Berlin)

Researchers: Wendelin Böhmer (Berlin)

Administration:

Associates:

Summary:

Reinforcement learning has emerged as an established theory for the control of autonomous agents in stochastic environments. Successful applications, however, are currently restricted to tasks which can be described with few variables, because the number of states is exponential in the number of state variables. Factored Markov decision process (MDP) methods aim to overcome this obstacle by imposing strong assumptions on possible value functions, i.e. to restrict the solution to linear approximations using basis functions with few variables in their respective domain. We hypothesize that, under some alternative assumptions, for every MDP there exist an unique factored state representation with optimal linear value approximation properties. To solve the control problem in large factored MDP we pursuit the following scientific goals:
(1) to extract a factored state representation tailored to the MDP at hand under some optimality criterion,
(2) to adapt existing algorithms so they can exploit this representation and efficiently solve large MDPs and
(3) to investigate the novel architecture to obtain approximation bounds and to assess how much information can be transferred between different tasks with this MDP.
The envisioned methods will give significant insight in the general problem of state representation and have the potential to break the curse of dimensionality in large factored MDP. As our assumptions restrict the solution much less than previous works, we expect to take on tasks in which approximation was impossible before.

Reinforcement learning hat sich als theoretisch fundierter Ansatz für die Steuerung von autonomen Agenten unter stochastischen Bedingungen erwiesen. Momentan sind erfolgversprechende Anwendungen jedoch auf Aufgaben mit wenigen Zustandsvariablen beschränkt, da die Anzahl von möglichen Zuständen exponentiell mit der Anzahl von Variablen wächst. Faktorisierende Markov Decision Process (MDP) Methoden versuchen, dieses Hindernis durch strikte Annahmen an die Value Funktion zu umgehen, indem sie die Lösung auf lineare Approximationen mittels Basisfunktionen, deren Wertebereich nur wenige Variablen einschließt, beschränken. Wir stellen die Hypothese auf, dass unter alternativen Annahmen jeder MDP eine faktorisierende Repräsentation besitzt, welche optimale Approximationseigenschaften aufweist.  Um das Steuerungsproblem in großen faktorisierenden MDPs zu lösen, werden wir folgende wissenschaftliche Ziele verfolgen:
(1) Ermittlung der optimalen faktorisierenden Repräsentation eines MDP an Hand eines Optimalitätskriteriums,
(2) Adaption von existierenden Lösungsalgorithmen an diese Repräsentation, um große faktorisierende MDPs effizient lösen zu können und
(3) Analyse der neuen Methode, um Schranken an den Approximationsfehler zu finden und möglichen Erfahrungstransfer zwischen Aufgaben zu untersuchen.
Die vorgeschlagenen Methoden sollen Einblick in das allgemeine Problem der Zustandskodierung geben und haben das Potential, den Curse of Dimensionality in großen faktorisierenden MDPs zu brechen. Da unsere Annahmen die Lösung im Vergleich zu bisherige Arbeiten weit weniger einschränken, erwarten wir auch Aufgaben lösen zu können, welche bisher als nicht approximierbar galten.

Phase 1 Projects

Value Representation in Large Factored State Spaces


Project leaders: Klaus Obermayer (Berlin)

Researchers: Wendelin Böhmer (Berlin)

Administration:

Associates:

Summary:

Reinforcement learning has emerged as an established theory for the control of autonomous agents in stochastic environments. Successful applications, however, are currently restricted to tasks which can be described with few variables, because the number of states is exponential in the number of state variables. Factored Markov decision process (MDP) methods aim to overcome this obstacle by imposing strong assumptions on possible value functions, i.e. to restrict the solution to linear approximations using basis functions with few variables in their respective domain. We hypothesize that, under some alternative assumptions, for every MDP there exist an unique factored state representation with optimal linear value approximation properties. To solve the control problem in large factored MDP we pursuit the following scientific goals:
(1) to extract a factored state representation tailored to the MDP at hand under some optimality criterion,
(2) to adapt existing algorithms so they can exploit this representation and efficiently solve large MDPs and
(3) to investigate the novel architecture to obtain approximation bounds and to assess how much information can be transferred between different tasks with this MDP.
The envisioned methods will give significant insight in the general problem of state representation and have the potential to break the curse of dimensionality in large factored MDP. As our assumptions restrict the solution much less than previous works, we expect to take on tasks in which approximation was impossible before.

Reinforcement learning hat sich als theoretisch fundierter Ansatz für die Steuerung von autonomen Agenten unter stochastischen Bedingungen erwiesen. Momentan sind erfolgversprechende Anwendungen jedoch auf Aufgaben mit wenigen Zustandsvariablen beschränkt, da die Anzahl von möglichen Zuständen exponentiell mit der Anzahl von Variablen wächst. Faktorisierende Markov Decision Process (MDP) Methoden versuchen, dieses Hindernis durch strikte Annahmen an die Value Funktion zu umgehen, indem sie die Lösung auf lineare Approximationen mittels Basisfunktionen, deren Wertebereich nur wenige Variablen einschließt, beschränken. Wir stellen die Hypothese auf, dass unter alternativen Annahmen jeder MDP eine faktorisierende Repräsentation besitzt, welche optimale Approximationseigenschaften aufweist.  Um das Steuerungsproblem in großen faktorisierenden MDPs zu lösen, werden wir folgende wissenschaftliche Ziele verfolgen:
(1) Ermittlung der optimalen faktorisierenden Repräsentation eines MDP an Hand eines Optimalitätskriteriums,
(2) Adaption von existierenden Lösungsalgorithmen an diese Repräsentation, um große faktorisierende MDPs effizient lösen zu können und
(3) Analyse der neuen Methode, um Schranken an den Approximationsfehler zu finden und möglichen Erfahrungstransfer zwischen Aufgaben zu untersuchen.
Die vorgeschlagenen Methoden sollen Einblick in das allgemeine Problem der Zustandskodierung geben und haben das Potential, den Curse of Dimensionality in großen faktorisierenden MDPs zu brechen. Da unsere Annahmen die Lösung im Vergleich zu bisherige Arbeiten weit weniger einschränken, erwarten wir auch Aufgaben lösen zu können, welche bisher als nicht approximierbar galten.