System and method for tree-based machine learning
Systems and methods of updating a multi-level data structure for controlling an agent. The method may include: accessing a data structure defining one or more nodes. A non-leaf node of the one or more nodes may be associated with one or more edges for traversing to a subsequent node. An edge of the one or more edges may be associated with a visit count and a softmax state-action value estimation. The method may include identifying a node trajectory including a series of nodes based on an asymptotically converging sampling policy, where the node trajectory includes a root node and a leaf node of the data structure, determining a reward indication associated with the node trajectory; and for at least one non-leaf node, updating the visit count and the softmax state-action value estimate associated with one or more edges of the non-leaf node based on the determined reward indication.
1. A method of updating a multi-level data structure for controlling an agent, the method comprising:
accessing a data structure defining one or more nodes, wherein a non-leaf node of the one or more nodes is associated with one or more edges for traversing to a subsequent node, and wherein an edge of the one or more edges is associated with a visit count and a softmax state-action value estimation;
for each of a plurality of rounds,
identifying a node trajectory including a series of nodes based on an asymptotically converging sampling policy, wherein the node trajectory includes a root node and a leaf node of the data structure;
determining a reward indication associated with the node trajectory; and
for at least one non-leaf node in the node trajectory, updating the visit count and the softmax state-action value estimate associated with one or more edges of the non-leaf node based on the determined reward indication associated with the node trajectory; and
for the leaf node in the node trajectory, updating statistics associated with the leaf node by;
N
(
s
L
)
←
N
(
s
L
)
+
1
V
^
(
s
L
)
←
V
^
(
s
L
)
+
R
-
V
^
(
s
L
)
N
(
s
L
)
wherein N(s L ) is a visit count associated with the leaf node, and wherein R is the reward indication, and wherein {circumflex over (V)}(s L ) is the mean state value.
2. The method of claim 1 , comprising determining an action for controlling the agent based on the maximum softmax state-action value estimation at a given node.
3. The method of claim 1 , wherein the asymptotically converging sampling policy is based on a distribution defined by:
π
t
(
a
)
=
(
1
-
λ
t
)
f
τ
(
r
^
)
(
a
)
+
λ
t
1
❘
"\[LeftBracketingBar]"
𝒜
❘
"\[RightBracketingBar]"
where λ t =ε| |/log(t+1) is a decay rate for exploration and the exploration parameter is ε>0.
4. The method of claim 1 , wherein the asymptotically converging sampling policy is associated with a mean squared error lower bound.
5. The method of claim 1 , wherein the softmax state-action value estimation is based on a softmax function defined by:
τ ( r )=τ log Σ a exp( r ( a )/τ)
where τ≥0 is a user-specified temperature parameter controlling a degree of exploration, and r(a) is a reward for an action a.
6. The method of claim 1 , wherein updating the visit count and the softmax state-action value estimate associated with one or more edges of the non-leaf node includes:
{circumflex over (Q)} sft ( s t ,a t )← {circumflex over (V)} sft ( s t+1 )
{circumflex over (V)} sft ( s t )← τ ( {circumflex over (Q)} sft ( s t ))
N ( s t ,a t )← N ( s t ,a t )+1,
wherein {circumflex over (Q)} sft (s t ) is a K dimensional vector, each component of which is {circumflex over (Q)} sft (s t , a) for action a, and wherein τ is a softmax function, and N(s t , a t ) is the state-action visit count.
7. The method of claim 1 , wherein determining a reward indication associated with the node trajectory is based on a Monte Carlo evaluation simulating the node trajectory from the root node to the leaf node of the data structure.
8. The method of claim 1 , comprising expanding the data structure by generating a further leaf node in the data structure, and wherein for at least one edge associated with the data structure, initialize visit count and softmax state-action value estimation to zero as defined by:
∀ a ∈ ( s L ) N ( s L ,a ), {acute over (Q)} sft ( s L ,a )←0
9. The method of claim 1 , wherein the data structure is a tree data structure.
10. A system for updating a multi-level data structure for controlling an agent, the system comprising:
a processor; and
a memory coupled to the processor and storing processor-executable instructions that, when executed, configure the processor to:
access a data structure defining one or more nodes, wherein a non-leaf node of the one or more nodes is associated with one or more edges for traversing to a subsequent node, and wherein an edge of the one or more edges is associated with a visit count and a softmax state-action value estimation;
for each of a plurality of rounds,
identify a node trajectory including a series of nodes based on an asymptotically converging sampling policy, wherein the node trajectory includes a root node and a leaf node of the data structure;
determine a reward indication associated with the node trajectory; and
for at least one non-leaf node in the node trajectory, update the visit count and the softmax state-action value estimate associated with one or more edges of the non-leaf node based on the determined reward indication associated with the node trajectory; and
for the leaf node in the node trajectory, updating statistics associated with the leaf node by:
N
(
s
L
)
←
❘
N
(
s
L
)
+
1
V
^
(
s
L
)
←
V
^
(
s
L
)
+
R
-
V
^
(
s
L
)
N
(
s
L
)
wherein N(s L ) is a visit count associated with the leaf node, and wherein R is the reward indication, and wherein {circumflex over (V)}(s L ) the mean state value.
11. The system of claim 10 , comprising processor-executable instructions that, when executed, configure the processor to determine an action for controlling the agent based on the maximum softmax state-action value estimation at a given node.
12. The system of claim 10 , wherein the asymptotically converging sampling policy is based on a distribution defined by:
π
t
(
a
)
=
(
1
-
λ
t
)
f
τ
(
r
^
)
(
a
)
+
λ
t
1
❘
"\[LeftBracketingBar]"
𝒜
❘
"\[RightBracketingBar]"
where λ t =ε| |/log(t+1) is a decay rate for exploration and the exploration parameter is ε>0.
13. The system of claim 10 , wherein the asymptotically converging sampling policy is associated with a mean squared error lower bound.
14. The system of claim 10 , wherein the softmax state-action value estimation is based on a softmax function defined by:
τ ( r )=τ log Σ a exp( r ( a )/τ)
where τ≥0 is a user-specified temperature parameter controlling a degree of exploration, and r(a) is a reward for an action a.
15. The system of claim 10 , wherein updating the visit count and the softmax state-action value estimate associated with the one or more edges of the non-leaf node includes:
{circumflex over (Q)} sft ( s t ,a t )← {circumflex over (V)} sft ( s t+1 )
{circumflex over (V)} sft ( s t )← ( {circumflex over (Q)} sft ( s t ))
N ( s t ,a t )← N ( s t ,a t )+1
wherein {circumflex over (Q)} sft (s t ) is a K dimensional vector, each component of which is {circumflex over (Q)} sft (s t , a) for action a, and wherein τ is a softmax function, and N(s t , a t ) is the state-action visit count.
16. The system of claim 10 , wherein determining a reward indication associated with the node trajectory is based on a Monte Carlo evaluation simulating the node trajectory from the root node to the leaf node of the data structure.
17. A non-transitory computer-readable medium or media having stored thereon machine interpretable instructions which, when executed by a processor, cause the processor to perform a computer implemented method of updating a multi-level data structure for controlling an agent, the method comprising:
accessing a data structure defining one or more nodes, wherein a non-leaf node of the one or more nodes is associated with one or more edges for traversing to a subsequent node, and wherein an edge of the one or more edges is associated with a visit count and a softmax state-action value estimation;
for each of a plurality of rounds,
identifying a node trajectory including a series of nodes based on an asymptotically converging sampling policy, wherein the node trajectory includes a root node and a leaf node of the data structure;
determining a reward indication associated with the node trajectory; and
for at least one non-leaf node in the node trajectory, updating the visit count and the softmax state-action value estimate associated with one or more edges of the non-leaf node based on the determined reward indication associated with the node trajectory; and
for the leaf node in the node trajectory, updating statistics associated with the leaf node by:
N
(
s
L
)
←
N
(
s
L
)
+
1
V
^
(
s
L
)
←
V
^
(
s
L
)
+
R
-
V
^
(
s
L
)
N
(
s
L
)
wherein N(s L ) is a visit count associated with the leaf node, and wherein R is the reward indication and wherein {circumflex over (V)}(s L ) is the mean state value.