I wish to train a reinforcement learning model to create a binary space partitioning (BSP) tree for any given unordered set of unique 2D points. In fact, I wish to create multiple RL models each incentivised towards a different goal. For example, one RL model could be incentivised to find the most balanced tree, another could be incentivised to form a tree with the least number of nodes, and yet another RL model incentivised to find the tallest tree.

It would appear that an RL model needs to be set up in a way that allows the agent to be able to do the following at every time step:

1) choose which cell (partition) to split next
2) choose a straight line to split the chosen cell into two new cells, so that the each point in the old (parent) cell now lies in one of the two new (child) cells.

In the beginning, all the given points can be considered to be inside a single cell.

But I'm struggling to represent the state space and the action space in this problem. Specificallly, 1. At any time step, the state comprises of a set of cells each containing a subset of the given points. I'm not sure how to design a feature vector to represent such a state.
2. The action involves choosing one of the cells to split. But the set of cells depends on the current state and their number is not fixed. I'm finding it difficult to design the policy function to work on a dynamic action space that's tied to the structure of the state.

Any help would be highly appreciated!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.