How to represent "terminate episode" for Knapsack problem with a Pointer Network?

Question

I am currently implementing a Pointer Network to solve a simple Knapsack Problem. However, I am a bit puzzled over the correct (or common, or "best") way to give the agent the option to stop taking the item (terminate episode). Currently, I have done it in 2 ways, adding raw dummy features or adding encoded dummy features (dummy features are all zeros). If the agent selects the dummy item, then the agent will stop taking the item anymore and the episode is terminated.

I trained both methods for 500K episodes and evaluated their performance on a single predefined test case in each episode, after adding the gradient. I found that concatenating dummy features with the encoded features yielded a higher score earlier, but also scored 0 very often. On the other hand, adding the dummy features to the raw features learned to maximize the score very slowly. Therefore, my questions are:

1. Is adding the raw dummy features make learning slower because of additional encoding layer learning?

2. What is the most correct (or common or arguably best) way to give the agent the option to terminate the episode (in this case stop taking item)?

Answer 1

I do not think there is one standard way to do this, it will depend too much on context. Ultimately you want the agent to output a stop action that is different from a continue action.

That stop/continue choice could either be part of the existing action encoding, additional data in parallel with the action sequence, or an entirely separate action choice on time steps alternating with the main action choices.

I do not know anything about pointer networks, so not sure what your action coding options are. Your "dummy" object selection seems like a reasonable choice though, it is part of existing action encoding that the neural network can already output. In that sense it seems a lot like an <END> token that a seq2seq model might output for e.g. translation or summarisation language tasks.

An alternative might be to add a separate head to the pointer network, that output a stop classifier alongside each object choice. The combined action would be [selection, stop]. If you are feeding previous choice back into the RNN as input (it is not clear to me, but sampling seq2seq networks do this), you have free choice as to whether to use the combined action (with the stop flag as a raw confidence in $[0,1]$), or just continue with previous selection as only feedback.

Finally you could use a different NN for deciding whether to stop or continue and feed it the same sequence.

Which is better? I cannot say, but your dummy object selection appears to work already to some degree, so I would stick experimenting with that, and the simple all zeroes token. The common 0 total rewards may be an issue with your RL agent exploring, or maybe with a difficult reward metric. E.g. can the agent score less than zero if it overfills the knapsack? If so, not trying anything at all may sometimes look good to the agent, and it will need more training so it can properly predict when this is not the case.

Answer 2

You can find information similar to exposed by Neil, but with more theoretical detail, in the book Deep Learning (Goodfellow et al., 2016) in the chapter 10 (Recurrent networks), more specifically in 10.2.3 Recurrent Networks as Directed Graphical Models and other subchapters.

Additional, related with pointer networks there are people changing the LSTM with Transformer (Learning Heuristics for the TSP by PolicyGradient, 2018)