2
$\begingroup$

I am currently completing my thesis on optimising combinatorial problems, and we decided to utilize reinforcement learning. The problem is that I am not sure which algorithm to choose. Is there a comprehensive table or guide to help me choose a model that works well for this domain or in general?

$\endgroup$
1
  • $\begingroup$ In my experience value based methods are more robust than policy gradient, though policy gradient are more flexible in how you define an action, so it really depends what you need. I would try and use an off-policy algorithm such as Deep Q-Learning or Soft Actor Critic to allow for more efficient use of all the data you’ll gather. $\endgroup$
    – David
    Commented Aug 4, 2022 at 8:13

1 Answer 1

2
$\begingroup$

From what I have read, the algorithm selection problem for deep reinforcement learning has been scarcely reviewed in the literature. To further complicate matters, DRL algorithms are notoriously sensitive to implementation details, hyperparameters, and the environment, making comparisons amongst algorithms inherently difficult.

One attempt at the algorithm selection problem in DRL is DeepMind's BSuite (paper, code, OpenReview). Even though the authors of BSuite do not claim to solve the algorithm selection problem, they state that it provides a "quick and dirty" comparison of algorithms. Considering that BSuite was accepted as a spotlight presentation at the recent 2020 ICLR conference and due to my own positive experience with the code, I am willing to advocate for its use.

DeepMind's BSuite is a suite of reinforcement learning environments that aim to "capture key issues in the design of efficient and general learning algorithms." The environments are designed to be "clear, informative and scalable." An example environment is the Deep Sea environment (see first picture) in which an agent may move down-left or down-right at each timestep and seeks the treasure. Moving down-left yields a reward of 0 while moving down-right yields a small negative reward. The dilemma is that the agent must always move down-right and accrue many small negative rewards to reach the treasure and receive a very large positive reward. An agent with strong exploration capabilities will realize that it needs to move down-right to explore the entire state space and ultimately reach the treasure even though it is receiving small negative rewards for each down-right movement. This environment (i) clearly tests exploration, (ii) is informative by discerning if an algorithm can find the treasure at a specific depth, and (iii) is quickly scalable to arbitrary sea depth.

enter image description here

Testing an algorithm on the entirety of BSuite yields a radar chart (see second picture) that allows for a crude comparison of algorithms on seven key issues of DRL. The motivation for BSuite is that the seven key issues tested by BSuite are prevalent issues in most other interesting environments.

enter image description here

To answer your question, see if the issues in optimizing combinatorial problems are similar to the ones investigated by BSuite. If so, BSuite may be very useful to determine the most promising algorithms for your application. If not, you may consider creating your own variant of BSuite by constructing clear, informative, and scalable environments that investigate common issues in optimizing combinatorial problems. Unfortunately, I don't recall ever seeing an archive of BSuite radar charts other than those shown in the paper, so you may need to run various algorithms on BSuite yourself if you indeed decide to use it.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .