Adaptive Control of Differentially Private Linear Quadratic Systems
Sayak Ray Chowdhury, Xingyu Zhou, Ness B. Shroff · NOT FOUND REPOSITORY (Indian Institute of Science Bangalore) · 2021
In this paper we study the problem of regret minimization in reinforcement learning (RL) under differential privacy constraints. This work is motivated by the wide range of RL applications for providing personalized service, where privacy concerns are becoming paramount. In contrast to previous works, we take the first step towards non-tabular RL settings, while providing a rigorous privacy guarantee. In particular, we consider the adaptive control of differentially private linear quadratic (LQ) systems. We develop the first private RL algorithm, Private-OFU-RL which is able to attain a sub-linear regret while guaranteeing privacy protection. More importantly, the additional cost due to privacy is only on the order of \\fracłn(1/δ)1/4\\varepsilon1/2 given privacy parameters \\varepsilon, δ > 0. Through this process, we also provide a general procedure for adaptive control of LQ systems under changing regularizers, which not only generalizes previous non-private controls, but also serves as the basis for general private controls. © 2021 IEEE., keywords=Control theory; Information theory; Privacy by design; Reinforcement learning, Adaptive Control; Additional costs; Differential privacies; Linear quadratic; Personalized service; Privacy concerns; Privacy protection; Regret minimization, Adaptive control systems, fundingdetails1=National Science FoundationNational Science Foundation, NSF, CNS-1901057, CNS-2007231, fundingdetails2=Office of Naval ResearchOffice of Naval Research, ONR, N00014-17-1-241, fundingtext1=However, in most practical scenarios, the feedback from the users often encodes their sensitive information. For example, in a personalized healthcare setting, the states of a patient include personal information such as age, gender, height, weight, state of the treatment etc. Similarly, the states of a virtual keyboard user (e.g., â��Equal contribution. This work was funded in part through NSF grants: CNS-1901057 and CNS-2007231, and an Office of Naval Research under Grant N00014-17-1-241 Google GBoard users) are the words and sentences she typed in, which inevitably contain private information about the user. Another intriguing example is the social robot for second language education of children. The states include facial expressions, and the rewards contain whether they have passed the quiz. Users may not want any of this information to be inferred by others. This directly results in an increasing concern about privacy protection in personalized services. To be more specific, although a user might be willing to share her own information to the agent to obtain a better tailored service, she would not like to allow third parties to infer her private information from the output of the learning algorithm. For example, in the healthcare application, we would like to ensure that an adversary with arbitrary side knowledge cannot infer a particular patientâ��s state from the treatments prescribed to her., references=1. Li, L., Chu, W., Langford, J., Schapire, R.E., A contextualbandit approach to personalized news article recommendation (2010) Proceedings of the 19th International Conference on World Wide Web, pp. 661-670; 2. Zhao, Y., Kosorok, M.R., Zeng, D., Reinforcement learning design for cancer clinical trials (2009) Statistics in Medicine, 28 (26), pp. 3294-3315; 3. Sharma, A.R., Kaushik, P., Literature survey of statistical, deep and reinforcement learning in natural language processing (2017) 2017 International Conference on Computing, Communication and Automation (ICCCA, pp. 350-354; 4. Gordon, G., Spaulding, S., Westlund, J.K., Lee, J.J., Plummer, L., Martinez, M., Das, M., Breazeal, C., Affective personalization of a social robot tutor for children's second language skills (2016) Proceedings of the Aaai Conference on Artificial Intelligence, 30 (1); 5. Dwork, C., Differential privacy: A survey of results (2008) International Conference on Theory and Applications of Models of Computation, pp. 1-19. , Springer; 6. Tossou, A., Dimitrakakis, C., Algorithms for differentially private multi-armed bandits (2016) Proceedings of the Aaai Conference on Artificial Intelligence, 30 (1); 7. Achieving privacy in the adversarial multi-armed bandit (2017) Proceedings of the Aaai Conference on Artificial Intelligence, 31 (1); 8. Basu, D., Dimitrakakis, C., Tossou, A., (2019) Differential Privacy for Multi-armed Bandits: What Is It and What Is Its Cost?; 9. Mishra, N., Thakurta, A., (nearly) optimal differentially private stochastic multi-arm bandits (2015) Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, pp. 592-601; 10. Zhou, X., Tan, J., Local Differential Privacy for Bayesian Optimization, p. 2020; 11. Balle, B., Gomrokchi, M., Precup, D., Differentially private policy evaluation (2016) International Conference on Machine Learning. Pmlr, pp. 2130-2138; 12. Vietri, G., Balle, B., Krishnamurthy, A., Wu, S., Private reinforcement learning with pac and regret guarantees (2020) International Conference on Machine Learning. Pmlr, pp. 9754-9764; 13. Garcelon, E., Perchet, V., Pike-Burke, C., Pirotta, M., Local Differentially Private Regret Minimization in Reinforcement Learning, p. 2020; 14. Abbasi-Yadkori, Y., Szepesvári, C., Regret bounds for the adaptive control of linear quadratic systems (2011) Proceedings of the 24th Annual Conference on Learning Theory, pp. 1-26; 15. Osband, I., Roy, B.V., Model-based reinforcement learning and the eluder dimension (2014) Proceedings of the 27th International Conference on Neural Information Processing Systems, 1, pp. 1466-1474; 16. Chowdhury, S.R., Gopalan, A., Online learning in kernelized markov decision processes (2019) The 22nd International Conference on Artificial Intelligence and Statistics. Pmlr, pp. 3197-3205; 17. Wang, T., Yang, L.F., Episodic Linear Quadratic Regulators with Low-rank Transitions, p. 2020; 18. Jin, C., Yang, Z., Wang, Z., Jordan, M.I., Provably efficient reinforcement learning with linear function approximation (2020) Conference on Learning Theory, pp. 2137-2143; 19. Bertsekas, D., Dynamic programming and optimal control (2004) Athena Scientific Belmont, , MA, 3 edition; 20. Dwork, C., Roth, A., (2014) The Algorithmic Foundations of Differential Privacy; 21. Kearns, M., Pai, M., Roth, A., Ullman, J., Mechanism design in large games: Incentives and privacy (2014) Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, pp. 403-410; 22. Bun, M., Steinke, T., Concentrated differential privacy: Simplifications, extensions, and lower bounds (2016) Theory of Cryptography Conference, pp. 635-658. , Springer; 23. Abbasi-Yadkori, Y., Pál, D., Szepesvári, C., Improved algorithms for linear stochastic bandits (2011) Advances in Neural Information Processing Systems, pp. 2312-2320; 24. Chan, T.-H.H., Shi, E., Song, D., Private and continual release of statistics (2011) Acm Transactions on Information and System Security (TISSEC, 14 (3), pp. 1-24; 25. Hsu, J., Huang, Z., Roth, A., Roughgarden, T., Wu, Z.S., Private matchings and allocations (2016) Siam Journal on Computing, 45 (6), pp. 1953-1984; 26. Vershynin, R., (2018) High-dimensional Probability: An Introduction with Applications in Data Science, 47. , Cambridge university press; 27. Laurent, B., Massart, P., Adaptive estimation of a quadratic functional by model selection (2000) Annals of Statistics, pp. 1302-1338, sponsors=IEEE Information Theory Society; The Institute of Electrical and Electronics Engineers, publisher=Institute of Electrical and Electronics Engineers Inc., issn=21578095, isbn=9781538682098, coden=PISTF, language=English, abbrevsourcetitle=IEEE Int Symp Inf Theor Proc, documenttype=Conference Paper, source=Scopus, @CONFERENCEVippathalla20211624, author=Vippathalla, PK and Chan, C and Kashyap, N and Zhou, Q, title=Secret Key Agreement and Secure Omniscience of Tree-PIN Source with Linear Wiretapper, journal=IEEE International Symposium on Information Theory - Proceedings, year=2021, volume=2021-July, pages=1624-1629, doi=https://doi.org/10.1109/ISIT45174.2021.9518075, note=The copyright for this article belongs to , url=https://www.scopus.com/inward/record.uri?eid=2-s2.0-85115053045&doi=10.11092fISIT45174.2021.9518075&partnerID=40&md5=76cafccf7a606fd4fc82a6b0c54bf9f7, affiliation=Indian Institute of Science, Department of Electrical Communication Engineering, Bangalore, 560012, India, abstract=In this paper, we obtain a single-letter characterization of the wiretap secret key capacity for a large class of multiterminal source models (namely, tree-PIN models) with a linear wiretapper that can observe arbitrary linear combinations of the source. For this class of sources, we also show a duality between the problems of wiretap secret key agreement and secure omniscience, which suggests that such duality potentially holds for more general sources. © 2021 IEEE., keywords=Forestry; Information theory, General source; Linear combinations; Multi terminals; Secret key agreement; Secret key capacities; Source models, Cryptography, fundingdetails1=21203318, fundingdetails2=Department of Science and Technology, Ministry of Science and Technology, IndiaDepartment of Science and Technology, Ministry of Science and Technology, India, डà¥�à¤�सà¤�à¥�, fundingtext1=C. Chan (email: [email protected]) is with the Department of Computer Science, City University of Hong Kong. His work is supported by a grant from the University Grants Committee of the Hong Kong Special Administrative Region, China (Project No. 21203318)., fundingtext2=N. Kashyap ([email protected]) and Praneeth Kumar V. ([email protected]) are with the Department of Electrical Communication Engineering, Indian Institute of Science, Bangalore 560012. Their work was supported in part by a Swarnajayanti Fellowship awarded to N. Kashyap by the Department of Science & Technology (DST), Government of India., references=1. Csiszar, I., Narayan,