IP Library › Granted Patent US 12,277,493
Granted Patent B2
US 12,277,493 · App. 16/876,866 · Granted Apr 15, 2025

Selecting action slates using reinforcement learning

Inventor: Peter Goran Sunehag (London, GB)
Assignee: DeepMind Technologies Limited
G06N3/08G06N3/088G06F16/90324
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,277,493
App. No.
16/876,866
Granted
Apr 15, 2025
Kind
B2
Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for selecting action slates using reinforcement learning. One of the methods includes receiving an observation characterizing a current state of an environment; selecting an action slate by processing the observation and a plurality of candidate action slates using a deep neural network, wherein each candidate action slate comprises a respective plurality of actions from the set of actions, and wherein the deep neural network is configured to, for each of the candidate action slates, process the observation and the actions in the candidate action slate to generate a slate Q value for the candidate action slate that is an estimate of a long-term reward resulting from the candidate action slate being provided to the action selector in response to the observation; and providing the selected action slate to an action selector in response to the observation.

Claims (70)

1. A method of providing a slate of actions to an action selector that interacts with an environment by selecting and performing actions, wherein the slate of actions includes a plurality of actions selected from a predetermined set of actions to fill a plurality of slots in an action slate, and wherein the environment transitions states in response to actions performed by the action selector, the method comprising:

receiving an observation characterizing a current state of the environment;

dividing the plurality of slots into a plurality of subsets;

selecting actions to fill in each subset, comprising, for a given subset of the plurality of subsets:

generating a plurality of candidate action slates for the given subset of slots, wherein each candidate action slate comprises a plurality of actions from the predetermined set of actions, wherein each candidate action slate for the given subset of slots has a same, predetermined number of slots with each slot being filled with a respective action from the predetermined set of actions, and wherein, for each candidate action slate, the slots are filled with a different combination of candidate actions from each of other candidate action slates for the given subset of slots;

for each candidate action slate, processing the candidate action slate using a deep neural network, wherein, for each candidate action slate, the deep neural network:

receives an input that comprises the plurality of actions in the candidate action slate and the observation, and

generates, as output, a slate Q value for the candidate action slate that is an estimate of a long-term reward resulting from the candidate action slate comprising the plurality of actions being provided to the action selector in response to the observation;

selecting a candidate action slate from the plurality of candidate action slates based on the slate Q values generated as output by the deep neural network for the candidate action slates; and

selecting, as the actions in the slots in the given subset, the actions in the slots in the selected candidate action slate;

generating a final action slate, wherein the final action slate comprises the selected actions for the slots in each subset; and

providing the final action slate to the action selector in response to the observation.

2. The method of claim 1 , wherein, in response to receiving the final action slate, the action selector performs either (i) an action selected from the final action slate or (ii) a null action that is not included in the predetermined set of actions.

3. The method of claim 1 , wherein generating the plurality of candidate action slates comprises, for the given subset of the plurality of subsets:

generating the plurality of candidate action slates for the given subset of the slots, each candidate action slate for the given subset of the slots including:

in any slot for which an action has already been selected, the action already selected for the slot,

a respective candidate action in each of the slots in the given subset, and

a respective placeholder action in any slot in the action slate other than the slots in the given subset and the slots for which an action has already been selected; and

wherein selecting the action slate comprises selecting as the actions, in the given subset of the slots in the action slate, the candidate actions that are in the slots in the given subset in the candidate action slate having a highest slate Q value.

4. The method of claim 3 , wherein the given subset of the slots has the predetermined number of slots that is greater than one.

5. The method of claim 3 , wherein the given subset of the slots has one slot.

6. The method of claim 3 , wherein the slots in the action slate are ordered from a highest slot in the action slate to a lowest slot in the action slate when provided to the action selector, and wherein selecting the action slate comprises selecting an action for each subset of slots in the action slate in sequence based on an ordering of the slots in the action slate when provided to the action selector.

7. The method of claim 3 , further comprising:

generating a random ordering of subsets of slots in the action slate, wherein selecting the actions to fill in each subset comprises selecting an action for each subset of slots in the action slate in sequence according to the random ordering.

8. The method of claim 3 , wherein, for each candidate action slate, the placeholder action is the same as one of the candidate actions in the given subset.

9. The method of claim 3 , wherein, for each candidate action slate, the placeholder actions are actions suggested by an external action recommendation system.

10. The method of claim 1 , wherein the actions in each candidate action slate are selected from a subset of the actions in the predetermined set of actions generated by an external process.

11. The method of claim 1 , further comprising:

receiving a reward in response to providing the final action slate to the action selector; and

using the reward in updating values of parameters of the deep neural network.

12. The method of claim 11 , wherein using the reward in updating the values of the parameters of the deep neural network comprises:

receiving a next observation characterizing a next state of the environment; and

using a current observation, the final action slate, the reward, and the next observation to update the values of the parameters of the deep neural network.

13. The method of claim 12 , wherein using the current observation, the final action slate, the reward, and the next observation to update the values of the parameters of the deep neural network comprises:

modifying the reward to generate a modified reward; and

using the modified reward in place of the reward in updating the values.

14. The method of claim 13 , wherein the modified reward satisfies r{circumflex over ( )}a, wherein r is the reward and a is a constant value greater than one.

15. The method of claim 1 , wherein the environment is a content item presentation setting provided by a content item recommendation system, wherein the action selector is a user of the content item recommendation system, wherein the actions in the predetermined set of actions are recommendations of content items, and wherein each action in the action slate is a recommendation of a distinct action to the user of the content item recommendation system.

16. The method of claim 1 , wherein the observation characterizing the current state includes data characterizing a preceding action that was selected by the action selector from a preceding slate of actions provided to the action selector in response to a preceding observation.

17. A system comprising one or more computers and one or more storage devices storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations for providing a slate of actions to an action selector that interacts with an environment by selecting and performing actions, wherein the slate of actions includes a plurality of actions selected from a predetermined set of actions to fill a plurality of slots in an action slate, and wherein the environment transitions states in response to actions performed by the action selector, the operations comprising:

receiving an observation characterizing a current state of the environment;

dividing the plurality of slots into a plurality of subsets;

selecting actions to fill in each subset, comprising, for a given subset of the plurality of subsets:

generating a plurality of candidate action slates for the given subset of slots, wherein each candidate action slate comprises a plurality of actions from the predetermined set of actions, wherein each candidate action slate for the given subset of slots has a same, predetermined number of slots with each slot being filled with a respective action from the predetermined set of actions, and wherein, for each candidate action slate, the slots are filled with a different combination of candidate actions from each of other candidate action slates for the given subset of slots;

for each candidate action slate, processing the candidate action slate using a deep neural network, wherein, for each candidate action slate, the deep neural network:

receives an input that comprises the plurality of actions in the candidate action slate and the observation, and

generates, as output, a slate Q value for the candidate action slate that is an estimate of a long-term reward resulting from the candidate action slate comprising the plurality of actions being provided to the action selector in response to the observation;

selecting a candidate action slate from the plurality of candidate action slates based on the slate Q values generated as output by the deep neural network for the candidate action slates; and

selecting, as the actions in the slots in the given subset, the actions in the slots in the selected candidate action slate;

generating a final action slate, wherein the final action slate comprises the selected actions for the slots in each subset; and

providing the final action slate to the action selector in response to the observation.

18. The system of claim 17 , wherein, in response to receiving the final action slate, the action selector performs either (i) an action selected from the final action slate or (ii) a null action that is not included in the predetermined set of actions.

19. The system of claim 17 , wherein generating the plurality of candidate action slates comprises, for the given subset of the plurality of subsets:

generating the plurality of candidate action slates for the given subset of the slots, each candidate action slate for the given subset of the slots including:

in any slot for which an action has already been selected, the action already selected for the slot,

a respective candidate action in each of the slots in the given subset, and

a respective placeholder action in any slot in the action slate other than the slots in the given subset and the slots for which an action has already been selected; and

wherein selecting the action slate comprises selecting as the actions, in the given subset of the slots in the action slate, the candidate actions that are in the slots in the given subset in the candidate action slate having a highest slate Q value.

20. One or more non-transitory computer storage media encoded with instructions that, when executed by one or more computers, cause the one or more computers to perform operations for providing a slate of actions to an action selector that interacts with an environment by selecting and performing actions, wherein the slate of actions includes a plurality of actions selected from a predetermined set of actions to fill a plurality of slots in an action slate, and wherein the environment transitions states in response to actions performed by the action selector, the operations comprising:

receiving an observation characterizing a current state of the environment;

dividing the plurality of slots into a plurality of subsets;

selecting actions to fill in each subset, comprising, for a given subset of the plurality of subsets:

generating a plurality of candidate action slates for the given subset of slots, wherein each candidate action slate comprises a plurality of actions from the predetermined set of actions, wherein each candidate action slate for the given subset of slots has a same, predetermined number of slots with each slot being filled with a respective action from the predetermined set of actions, and wherein, for each candidate action slate, the slots are filled with a different combination of candidate actions from each of other candidate action slates for the given subset of slots;

for each candidate action slate, processing the candidate action slate using a deep neural network, wherein, for each candidate action slate, the deep neural network:

receives an input that comprises the plurality of actions in the candidate action slate and the observation, and

generates, as output, a slate Q value for the candidate action slate that is an estimate of a long-term reward resulting from the candidate action slate comprising the plurality of actions being provided to the action selector in response to the observation;

selecting a candidate action slate from the plurality of candidate action slates based on the slate Q values generated as output by the deep neural network for the candidate action slates; and

selecting, as the actions in the slots in the given subset, the actions in the slots in the selected candidate action slate;

generating a final action slate, wherein the final action slate comprises the selected actions for the slots in each subset; and

providing the final action slate to the action selector in response to the observation.

Assignments (3)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 6, 2025
From: DEEPMIND TECHNOLOGIES LIMITED
To: GDM HOLDING LLC
Reel/Frame 071498/0210 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 19, 2020
From: SUNEHAG, PETER GORAN
To: GOOGLE INC.
Reel/Frame 052987/0945 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 19, 2020
From: GOOGLE INC.
To: DEEPMIND TECHNOLOGIES LIMITED
Reel/Frame 052988/0001 →
Continuity (3)
Continuation 15367094 · Dec 1, 2016
Provisional Application 62261781 · Dec 1, 2015
Related Publication 20200279162A1 · Sep 3, 2020
References Cited (44)
US 20070174105A1 · Abe et al. · 2007 [cited by applicant]
US 20150100530A1 · Mnih et al. · 2015 [cited by applicant]
US 20150206031A1 · Lindsay et al. · 2015 [cited by applicant]
CN 1774224 · 2006 [cited by applicant]
CN 103678669 · 2014 [cited by applicant]
CN 103914560 · 2014 [cited by applicant]
WO WO2015054264 · 2015 [cited by applicant]
Fard et al (“Non-Deterministic Policies in Markovian Decision Processes”, Journal of Artificial Intelligence Research 40 (2011), pp. 1-14) (Year: 2011). [cited by examiner]
He et al (“Deep Reinforcement Learning with an Unbounded Action Space”, https://arxiv.org/abs/1511.04636, arXiv:1511.0463v2 [cs.AI], Nov. 19, 2015, pp. 1-15) (Year: 2015). [cited by examiner]
Kale et al (“Non-Stochastic Bandit Slate Problems”, Advances in Neural Processing Systems 23 (NIPS 2010), 2010, pp. 1-9) (Year: 2010). [cited by examiner]
Kanade et al (“Sleeping Experts and Bandits with Stochastic Action Availability and Adversarial Rewards”, Proceedings of the 12th International Conference on Artificial Intelligence and Statistics (AISTATS) 2009, pp. 27… [cited by examiner]
K. Efthymiadis (“Knowledge-Based Reward Shaping with Knowledge Revision in Reinforcement Learning”, University of York, Computer Science, PHD Dissertation, Sep. 2014, pp. 1-119) (Year: 2014). [cited by examiner]
Prashanth L. A. (“Cumulative Prospect Theory Meets Reinforcement Learning: Prediction and Control”, https://arxiv.org/pdf/1506.02632v2.pdf, arXiv:1506.02632v2 [cs.LG] Sep. 20, 2015, pp. 1-27) (Year: 2015). [cited by examiner]
Chen et al. (“Combinatorial Multi-Armed Bandit: General Framework, Results and Applications”, Proceedings of the 30th International Conference on Machine Learning, JMLR: W&CP vol. 28, 2013, pp. 1-9) (Year: 2013). [cited by examiner]
Mahdi Milani Fard (“Non-Deterministic Policies in Markovian Processes”, Master Thesis, McGill University, Jun. 16, 2009, pp. 1-99) (Year: 2009). [cited by examiner]
Pazis, J., et al, Generalized Value Functions for Large Action Sets, received [Feb. 20, 2024]. . . Retrieved from Internet :<chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://icml.cc/2011/papers/609_icmlpaper.… [cited by examiner]
Dahlstrom, D., et al, Imitative Policies for Reinforcement Learning, [received on Feb. 20, 2024]. Retrieved from Internet:<chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://cseweb.ucsd.edu/˜ddahlstr/cse254/200… [cited by examiner]
Carbonell et al. “The use of MMR, diversity-based reranking for reordering documents and producing summaries,” Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information… [cited by applicant]
Dulac-Arnold et al. “Fast reinforcement learning in large discrete action spaces,” arXiv preprint arXiv 1512.07679v2, Apr. 4, 2016, 11 pages. [cited by applicant]
Efthynniadis, “Knowledge-Based Reward Shaping with Knowledge Revision in Reinforcement Learning”, University of York, Computer Science, PHD Dissertation, Sep. 2014, 1-119. [cited by applicant]
EP Communication Pursuant to Article 94(3) EPC in European Appln. No. 16816522.3, dated Jan. 8, 2020, 9 pages. [cited by applicant]
Fard et al. “Non-deterministic policies in markovian decision processes,” Journal of Artificial Intelligence Research, Jan. 1, 2011, 24 pages. [cited by applicant]
International Search Report and Written Opinion in International Application No. PCT/US2016/064476, mailed on Mar. 7, 2017, 14 pages. [cited by applicant]
Jarvelin et al. “Cumulated gain-based evaluation of it techniques,” ACM Transaction on Information Systems, 20.4, Oct. 1, 2002, 30 pages. [cited by applicant]
Kahneman et al. “Prospect theory: An analysis of decisions under rise,” Econometrica, vol. 47.2, Mar. 1979, 33 pages. [cited by applicant]
Kale. “Non-Stochastic Bandit Slate Problems,” Advances in Neural Information Processing Systems, 2010, 9 pages. [cited by applicant]
Kanade et al., “Sleeping Experts and Bandits with Stochastic Action Availability and Adversarial Rewards”, Proceedings of the 12th International Conference on Artificial Intelligence and Statistics (AISTATS) 2009, 272-2… [cited by applicant]
Kimura et al. “Reinforcement learning in multi-dimensional state-action space using random rectangular course coding and Gibbs sampling,” IEEE/RSJ International Conference on Intelligent Robots and Systems, Oct. 29, 200… [cited by applicant]
Kveton et al. “Matroid bandits: Fast combinatorial optimization with learning,” arXiv preprint arXiv 1403.5045v3, Mar. 20, 2014, 12 pages. [cited by applicant]
Lillicrap et al. “Continuous control with deep reinforcement learning,” arXiv preprint arXiv1509.02971v5, Feb. 29, 2016, 14 pages. [cited by applicant]
Onda et al. “A reinforcement learning model using macro-actions in multi-task grid-world problems,” IEEE International Conference on Systems, Man and Cybernetics, Oct. 11, 2009, 6 pages. [cited by applicant]
Ong et al. “Distributed Deep Q-Learning,” CME 323: Distributed Algorithms and Optimization, Spring 2015, Stanford University, Aug. 17, 2015, 8 pages. [cited by applicant]
Sunehag et al. “Deep Reinforcement Learning with Attention for Slate Markov Decision Processes with High-Dimensional State and Actions,” arXiv preprint arXiv 1512.01124, Dec. 3, 2015, 15 pages. [cited by applicant]
Office Action in Chinese Appln. No. 201680070828.1, dated Sep. 27, 2021, 24 pages (with English translation). [cited by applicant]
Maillard, “Apprentissage Sequentiel: Bandits, Statistique, et Renforcennent,” Machine Learning, Universite des Sciences et Technologie de Lille—Lille I, 2011, 1-319. [cited by applicant]
Mnih et al., “Human-level control through deep reinforcement learning,” Nature, Feb. 25, 2015, 518:529-533. [cited by applicant]
Ng et al., “Autonomous inverted helicopter flight via reinforcement learning,” Experimental Robotics IX, Springer Berlin Heidelberg, 2006, 10 pages. [cited by applicant]
Park et al., “A literature review and classification of recommender system research,” Expert Systems with Applications, Sep. 1, 2012, 39(11):14 pages. [cited by applicant]
Russel et al., “Artificial Intelligence: A Modern Approach,” Artificial Intelligence, Prentice Hall, Egnlewood Cliffs, 1995, 25(27):10 pages. [cited by applicant]
Silver et al., “Deterministic policy gradient algorithms,” Proceedings of the 31st International Conference on Machine Learning, Jun. 2014, 32(1):387-395. [cited by applicant]
Silver et al., “Concurrent Reinforcement Learning from Customer Interactions,” Proceedings of the 30th International Conference on Machine Learning, 2013, 28(3):924-932. [cited by applicant]
Van Hasselt et al., “Using continuous action spaces to solve discrete problems,” 2009 International Joint Conference on Neural Networks, Jun. 2009, 8 pages. [cited by applicant]
Yue et al. “Linear submodular bandits and their application to diversified retrieval,” Advances in Neural Information Processing Systems, 2011, 9 pages. [cited by applicant]
Notification to Grant Patent Right for Invention in Chinese Appln. No. 201680070828.1, dated May 24, 2022, 8 pages (with English translation). [cited by applicant]