Q-Learning Without Complete Training Data

Question

I am implementing Q-Learning to find the "Next Best Action" a sales rep should take on a particular account to collect more money.

I am feeding the algorithm past actions taken on the accounts and the resulting states from those actions in order to learn the Q matrix. My problem is not every account had all available actions taken on it.

So in the first iteration of the Q-Learning algorithm we randomly select an initial state s (In my application this would be a unique account z AND state s combination). We then randomly chose an action a to execute. Unfortunately we may not have a ever taken action a on that particular account z, and as a result cannot observe any resulting state s'. Note: State transitions are constrained to one account. For example: I can't invoke an action a on account z1 and observe the resulting state on a different account z2.

If this scenario occurs should I just end the episode? However I never reached the goal state. Do I violate any assumptions for ending the episode early for reasons other than reaching the goal state?

Is there a better way to implement Q-Learning using past data that does not include records for all state and action combinations?

Should I even be using Reinforcement Learning, or should I use Markov Decision Processes since I can compute the transition matrix using my past records of the system?

Answer 1

I would approach the problem in the following way.

1. Cluster the accounts so that the state is (account cluster, state of the account)
2. Construct the transition matrices with de data you have available.
3. Use Dynamic programming to find the optimal policy.
4. Force the sales representatives to follow the actions of Q-learning. So that it implements the optimal policy found by dynamic programming most of the time and takes a random action from time to time (greedy exploration)
5. Q-Learning will be start gathering more data and modifing the best policy.

Step 1. Would help reduce the dimensionality of the problem. It will be useful with new accounts, since you would be able to use the best policy found in other accounts.

Steps 2. and 3. would use the data you have to construct the best static policy so far. This will make the Q-learning have a better start.

Steps 4. and 5. would help you balance the tradeoff between gathering data to construct the optimal policy and actually helping the sales representatives gathering more money.

Answer 2

I found an important statement from Francisco S. Melo of the Institute for Systems and Robotics, Instituto Superior Técnico, Lisboa, PORTUGAL, which might help you:

"Theorem 1.[...] the Q-learning algorithm, given by the update rule [math formula] converges w.p.1 to the optimal Q-function as long as [...] all state-action pairs be visited infinitely often."[1]

So, if you aim to have the optimal Q-function and thus to obtain the optimal policy, then the answer should be: yes, you need for each state all possible actions according to the above quote.

However, I am not sure, if RL is the right tool here, because recall that in RL actions should bring you from one state to another state. I am not sure, if an action is taken on one account (I understood that your state is formed by a tuple (acc_id, some account attributes list) correct?), how would you go from that state to another?

E.g. lets assume initial state is (id:0, {age:20, income:1000}) -> (do some action) -> Transition to state (id:2, {age:35, income:2000}).

What about reading on recommendation systems, since your problem seems to be closely related to it, at least this is my impression? See [2]. It seems that you want to recommend an action based on some attributes of an account.

Hope that helps a bit :).

[1] http://users.isr.ist.utl.pt/~mtjspaan/readingGroup/ProofQlearning.pdf

[2]Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions