1
$\begingroup$

I want know how to add a constraint to Q-learning. I have an action resulting in two rewards every time (reward 1= delivery cost , reward 2= delivery time). I want to minimize the cost while ensuring max delivery time limit is not violated. Is there a standard/formalized way to do this?

$\endgroup$
  • 1
    $\begingroup$ OP, I think Neil and I are in agreement, you need to clarify your question (see comments below). $\endgroup$ – www3 Nov 29 '17 at 15:28
1
$\begingroup$

Is there a standard/formalized way to do this?

Yes. There is no way to optimise across two independent variables, they must be combined into a single metric. This is typically done using a linear sum. If one value must be minimised and the other maximised, then typically in RL you express the value to be minimised as a negative reward value, because RL usually maximises reward (this is not a requirement, you can easily re-write any RL algorithm to minimise a long-term cost, just the literature mostly talks about maximising a long-term reward).

So you must combine the two metrics, decide the weights for the disparate rewards, perhaps based on monetary business value. Then you add them together. If there are strict constraints, either ensure action or state space does not allow the possibility of them, or if that is not feasible, then penalise an unacceptable result with a large negative reward. There is no requirement that you scale rewards linearly.

$\endgroup$
  • 1
    $\begingroup$ I interpreted his question differently. I interpreted it as reward 1 is the true reward and reward 2 is really a constraint. So in the RL framework, you do your rollouts and then if Sum of reward_2 > A the game ends or whatever and Sum of reward_1 is your total reward, i.e. this is the knapsack problem. $\endgroup$ – www3 Nov 28 '17 at 20:59
  • $\begingroup$ @www3: There isn't really anything in RL to apply that kind of constraint. Because it is not a constraint of the environment, but an undesirable outcome in an unconstrained environment. You have to treat it a like crashing a self-driving car -> assign a high cost. Maybe end episode early too, if that makes sense. $\endgroup$ – Neil Slater Nov 28 '17 at 21:18
  • 1
    $\begingroup$ At the very least you are misinterpreting me. I'm not an expert in RL, but this is easily implemented. See for example here: arxiv.org/pdf/1611.09940.pdf (Knapsack section) $\endgroup$ – www3 Nov 29 '17 at 14:56
  • $\begingroup$ @www3: It could well be a good match between OP's original problem and Knapsack . . . but that will depend on details of the actions available and more specifics of the MDP, which are not given. My answer attempts not to make any assumptions and just focuses on how to use two different reward signals. It may help to clarify with OP some details, so you would know better if your interpretation is accurate. If it is, I'd encourage you to put together a more focused answer. Specific constraints may have specific solutions. $\endgroup$ – Neil Slater Nov 29 '17 at 15:20
  • $\begingroup$ @www3: I think my answer covers Knapsack as described in the linked example with "ensure action or state space does not allow the possibility of them" - it is not 100% clear, but it looks like to me that the Knapsack logic was implemented as a strict rule in the environment code, so it was not possible at all to exceed capacity through taking any action. This is not always an option if your agent is taking actions in the real world (e.g. trying to insert objects into real boxes). $\endgroup$ – Neil Slater Nov 29 '17 at 15:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.