Admissible policy teaching through reward design
We study reward design strategies for incentivizing a reinforcement learning agent to adopt a policy from a set of admissible policies. The goal of the reward designer is to modify the underlying reward function cost-efficiently while ensuring that any approximately optimal deterministic policy unde...
| Main Authors: | , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Association for the Advancement of Artificial Intelligence
2022
|
| _version_ | 1797107178666983424 |
|---|---|
| author | Banihashem, K Singla, A Gan, J Radanovic, G |
| author_facet | Banihashem, K Singla, A Gan, J Radanovic, G |
| author_sort | Banihashem, K |
| collection | OXFORD |
| description | We study reward design strategies for incentivizing a reinforcement learning agent to adopt a policy from a set of admissible policies. The goal of the reward designer is to modify the underlying reward function cost-efficiently while ensuring that any approximately optimal deterministic policy under the new reward function is admissible and performs well under the original reward function. This problem can be viewed as a dual to the problem of optimal reward poisoning attacks: instead of forcing an agent to adopt a specific policy, the reward designer incentivizes an agent to avoid taking actions that are inadmissible in certain states. Perhaps surprisingly, and in contrast to the problem of optimal reward poisoning attacks, we first show that the reward design problem for admissible policy teaching is computationally challenging, and it is NP-hard to find an approximately optimal reward modification. We then proceed by formulating a surrogate problem whose optimal solution approximates the optimal solution to the reward design problem in our setting, but is more amenable to optimization techniques and analysis. For this surrogate problem, we present characterization results that provide bounds on the value of the optimal solution. Finally, we design a local search algorithm to solve the surrogate problem and showcase its utility using simulation-based experiments. |
| first_indexed | 2024-03-07T07:12:18Z |
| format | Conference item |
| id | oxford-uuid:7359b22a-e146-4906-8381-06f476fb78ad |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:12:18Z |
| publishDate | 2022 |
| publisher | Association for the Advancement of Artificial Intelligence |
| record_format | dspace |
| spelling | oxford-uuid:7359b22a-e146-4906-8381-06f476fb78ad2022-07-06T09:58:45ZAdmissible policy teaching through reward designConference itemhttp://purl.org/coar/resource_type/c_5794uuid:7359b22a-e146-4906-8381-06f476fb78adEnglishSymplectic ElementsAssociation for the Advancement of Artificial Intelligence2022Banihashem, KSingla, AGan, JRadanovic, GWe study reward design strategies for incentivizing a reinforcement learning agent to adopt a policy from a set of admissible policies. The goal of the reward designer is to modify the underlying reward function cost-efficiently while ensuring that any approximately optimal deterministic policy under the new reward function is admissible and performs well under the original reward function. This problem can be viewed as a dual to the problem of optimal reward poisoning attacks: instead of forcing an agent to adopt a specific policy, the reward designer incentivizes an agent to avoid taking actions that are inadmissible in certain states. Perhaps surprisingly, and in contrast to the problem of optimal reward poisoning attacks, we first show that the reward design problem for admissible policy teaching is computationally challenging, and it is NP-hard to find an approximately optimal reward modification. We then proceed by formulating a surrogate problem whose optimal solution approximates the optimal solution to the reward design problem in our setting, but is more amenable to optimization techniques and analysis. For this surrogate problem, we present characterization results that provide bounds on the value of the optimal solution. Finally, we design a local search algorithm to solve the surrogate problem and showcase its utility using simulation-based experiments. |
| spellingShingle | Banihashem, K Singla, A Gan, J Radanovic, G Admissible policy teaching through reward design |
| title | Admissible policy teaching through reward design |
| title_full | Admissible policy teaching through reward design |
| title_fullStr | Admissible policy teaching through reward design |
| title_full_unstemmed | Admissible policy teaching through reward design |
| title_short | Admissible policy teaching through reward design |
| title_sort | admissible policy teaching through reward design |
| work_keys_str_mv | AT banihashemk admissiblepolicyteachingthroughrewarddesign AT singlaa admissiblepolicyteachingthroughrewarddesign AT ganj admissiblepolicyteachingthroughrewarddesign AT radanovicg admissiblepolicyteachingthroughrewarddesign |