Scale By The Bay 2020: Robert J. Neal, A Reinforcement Learning Framework in Scala 3

Scale By The Bay 2020: Robert J. Neal, A Reinforcement Learning Framework in Scala 3

Recording: Scale By The Bay 2020: Robert J. Neal, A Reinforcement Learning Framework in Scala 3

[Music] yeah uh so i'm robert neal i'm a software engineer at twitter um today i'm going to be talking about a personal project that i've been working on which is the reinforcement learning library in uh scholar three and um to talk about the an implementation of that using that library um my daughter aaron will be speaking as well hi um i'm mary o'neal i'm a freshman at two high school in san francisco cool so uh first let me set set up this library so to be clear this library isn't a library that's meant to be put into production and scale it's really a library for testing algorithms and learning algorithms and to help understand what i mean there i'll talk a little about the motivation so the motivation is two-fold so one motivator was um a reinforcement learning reading group that we did at twitter uh last year so like many reading groups um each week a different person would sort of dive into the details of um the book we were reading uh and you know put together some sort of a summary and talk about the details of that week's reading but inevitably what would happen and this happens in a lot of reading groups is the other people in the reading group you know would have other things that they were responsible for they'd get distracted they wouldn't be able to dive in as deep as the presenter um and so one thing that i found that works really well in reading groups whether they're machine learning reading groups or category theory reading groups is having everybody in the reading group implement the week's reading and one one way that would facilitate that is if you had a library for for doing so for reinforcement learning so that was one of the motivators another motivator was um a talk that we had last year from an intern who was working on reinforcement learning for their phd and written this paper um with a novel algorithm for reinforcement learning and one of the things that you see when you're reading papers and reinforcement learning is that you know these new algorithms are are often written because an older algorithm doesn't work well in a particular scenario so when you see the simulations that show that this algorithm is better it's better for the particular scenario that the paper is writing about but you might want your own testbed to test whether or not it works well in your scenario or just to understand you know how the parameters affect it in different scenarios so those are sort of motivations for creating this reinforcement learning library and um so next i'll talk a little bit about what reinforcement learning is for those of you who are less familiar so reinforcement learning is really one of three categories of machine learning so there's supervised learning unsupervised learning and reinforcement learning and uh if you're familiar with machine learning you're most likely most familiar with supervised learning and supervised learning typically is the case where you have some model you train it on some data and you know once you get the model that you like you put into production and it gives you some deterministic predictions for some input so you might have for example a model that predicts whether or not somebody's going to click on a button in a conversion funnel and so for that particular user you might predict say with 0.7 probability they're going to click on this button so you show them the button and it might turn out that they don't click on the button but next week when somebody else comes with similar user features you still get a 0.7 probability that they're going to click on the button reinforcement learning one of the ways in which it's different is that it's learning as it goes uh so you know if it decides to show a button to a person and that person doesn't click the button it incorporates that information into its decision next time to show a button to someone with similar features so it's a little bit how the two are different and i'm going to start with a really simple example um a relatively simple example so multi-armored bandits are something that you might be familiar with and they're actually a simple case of reinforcement learning and what makes the mix and the simple case is that the reinforcement learning problems where there's only one state so what you have is you have a state with particular actions you can take and these actions are the arms on the multi-armed bandit so in this case we have a three-armed bandit so there's three actions we can take but they're all from the same state so i'm in some state and i can take some action and get some reward um but then after i take that action and get that reward i can then take some other action from that same state so really all i have to think about is which action should i take and what is the reward structure and so remember we don't have to to train the model but beforehand we can just throw it out there with it not knowing anything about these reward structures and then it will learn as it goes which one it wants to pick and what's trying to do is find what's called an optimal policy which is um you know what which action should it take and when uh for a particular um state and environment and so what we're trying to do here is trying to understand what is this um distribution from which these rewards are being sampled so remember multiple bandits are named after one armed bandits which is a colloquialism for slot machines and uh they're called one armed bandits because in the long run um and i hate to burst anybody's bubble but if you play slot machines long enough you're gonna lose money uh so i hope that doesn't ruin anyone's weekend plans but it turns out that um you know casinos actually win in the long run so so you pull this arm and in order to keep you there obviously they're not just going to take your money every time some of the time they're going to give you some reward and those rewards aren't always going to be the same so you're not always going to hit the jackpot sometimes maybe you get two sevens and a cherry and so you get a little bit of reward sometimes maybe you get you know three bars and you get some other type of some other amount of reward and um thinking about the multi-iron bandit the idea here is that for each arm that you pull the reward structure is different and you want to figure out which arm should you be pulling but you don't have any initial information up front so you want to know you know what is the reward for this particular arm or you can think of it as three different spot machines so if you have the option between three different slot machines which one should you be playing uh and so you'll want some way of deciding which action should i take and let's say that you take action one and you get reward one and let's say that you win a little bit of money so should you always just keep playing that same slot machine um you might think so because you know the reward for that is positive and all the other ones are unknown so maybe you think of them as zero but really you want to balance this exploiting the fact that you know that this one pays out and exploring these other ones that way you minimize regret the regret that like maybe you chose wrong in the future and it produced a lot of wrong consequences so this is sort of a simple problem and it's often used in things like conversion funnels or online for things like a type of testing or experimentation online um but then it generalizes into the reinforcement learning problem which you can really think of uh to simplify it as just this multi-armor dependent problem where after you take some action and you get some reward you actually transition to a different state so thinking of like a more complex reinforcement learning problem let's say that you had um a robot who was in a room and their job was to pick up aluminum cans and recycle them um well the environment here is is this room and when i pick up an aluminum can to recycle it actually the state of the room changes so whereas in the first state there is this option to pick up this aluminum can and recycle it after i recycle it i'm in some new state where this option isn't available or maybe i move around the room so my state changes and the actions available to me are different and depending on which action i take the rewards are different so you can imagine i'm in state one i take action one now i'm in state two maybe i take action five not even state three uh and it's uh added complexity on top of a single state problem so now how do we model this so this is sort of the goal of the library is to model this in a way that's easy for learning and comparing different reinforcement learning algorithms and you can think of it as really just two key components so it's actually sort of simple to model so one piece is the agent and the other piece is the environment and the agent is just the thing that acts and the environment is just the thing that you act in so the agent you know takes some actions in the environment and gets some rewards and potentially the environment also changes states so how do you know which action to pick well there are different methods for picking it but the context in which we'll talk about it now is a tabular context where we actually want to keep a record of for each state and action the rewards the reward values so you can imagine this table representing for state one and action one of all the times that i've taken that action in that state maybe i i'm averaging the reward and the average reward is point two and then likewise for action 2 in that same state my average reward is negative 7.9 so if i'm simply just picking the best option and i want to maximize the reward i'm going to go with action one and then what i do with this table is every time i take an action i get some new reward and then i incorporate it into the average so that the next time i take an action i have updated information and of course this is really easily represented functionally as just giving me the state and then giving me the action and then i give you some some reward so let me talk a little bit about how to model this uh in scala so of course one thing we have is environment and environment is really pretty straightforward it's just all the possible states um and the all the possible actions for each of those states and then of course because this is immutable we want the current state that we're in and then environment has a method on it called act and when you act in the environment it returns another environment with the state updated and then of course the agent needs to use this environment and the agent actually has different goals that it could be targeting so one is a reward one is a preference right now but there could be other types of goals and then it uses the environment to act in and then there are two key parameters here so one is the action selector and this is really maybe the core of the the usefulness of the library because the action selector are really the algorithms for deciding which action to to choose and this is a lot of times what you'll want to be comparing when you're comparing different algorithms for reinforcement learning so one example of an action selector and maybe the most popular is epsilon greedy and with epsilon greedy what it does is some percentage of the time say say 90 it will just always pick the best option and then say 10 percent of the time it will explore randomly all of the other actions that way it doesn't lose out on a potentially better action but it also is able to maximize the rewards but there are other action selectors as well another common one is upper confidence bound where you want to incorporate the uncertainty in your estimate of the reward so if you have a lot of uncertainty you might want to keep exploring that until you get enough information to reduce your uncertainty in that estimate so the nice thing here is that the agent allows you to really easily pass in these algorithms and there's a bunch already in the library but you could write your own custom action selector and pass it into the agent very easily the other piece is the updater updater is just an another function and this function is used for updating that table we've talked about so um you might just use the sample average which is just you know averaging the reward over all the times that you've taken that action but in other cases you might have like a non-stationary environment where as time goes on actually the reward structure changes so if that happens one thing you might think is that you don't want to wait the rewards that happened a long time ago as much as the ones that happened more recently because you think the ones that are more recent are going to be more indicative of rewards that you're going to see in the future so there you might want to use something like an exponential recency weighted average so these things are available in the library as well and you can you can swap them in and out and then the last piece here is just um that table that we talked about where it's really just a map from state to actions and rewards so this is sort of a very high level just the interface for the agent and the environment and to talk about like how you might implement this concretely aaron's going to talk about a game that she wrote uh using the reinforcement learning library so here's my example as you probably know tic-tac-toe is this game where there are two players one assigned one is assigned x the other's assigned o and they take turns filling this three by three array and attempt to get three in a row before the other so for my example the ui is implemented in react and the server is implemented in aca http which uses the reinforcement learning library so the environment the computer is navigating is this tic-tac-toe board and the environment is holding all the states that the computer could possibly encounter as well as all the actions that the computer can take from those states so for winning state values the state values are equal to one and the losses in draws states are equal to zero and all other state values start off as 0.5 and are updated as the computer plays and learns so the way that the computer chooses chooses actions is by exploiting the state with the highest value 90 of the time and 10 of the time exploring randomly selecting different actions and to update the states when the computer exploits 0.9 of the state that it exploited to will go back and average out with the previous state and that will update the previous state value when the computer explores however the previous state value isn't updated at all so like i said the environment is holding these um possible states as well as the possible state actions and the way we're generating these states is we're giving this function and an empty array and the function is alternating putting x's and nose onto the array also with some blanks in order to make possible states and the reasons alternating is so that it doesn't make any impossible states that the computer will never encounter such as a board full of x's which just isn't possible so here is where um here's where the computer is being told what the computer can do in those states where where the computer can place its o and here is where um the state values are the initially being given all the winning states are being given a value of one all the losing all the losses and draws are being given being given a value of zero and all the all other values are starting as 0.5 so here's the computer the computer is using epsilon greedy um which is when it 90 of the time exploits the highest state value and 10 of the time explores and it's also using temporal difference learning method where it gives 0.9 of the state that exploited 2 back to the previous state and averages out with the previous state's value so here's an example of the tic-tac-toe um computer actually playing so the computer is playing against a player that's imperfect that doesn't immediately get those wins as fast as maybe two players who experienced their playing um just to give the the computer in an opportunity to update its state values and see how it can win how it loses so um as the compute as the player and the computer are playing the player is going to those thing values and when the computer loses those state values are decreasing and so the computer when it's exploiting won't go there and when it finds a way to win those state values are increasing so when the computer exploits nine percent of the time the computer will continue to go there and if it's not going there it's exploring the other ten percent of the time so now to talk about scholarly speeches okay cool so that that's a a nice example of how you know with actually very minimal code you can write a nice implementation of a reinforcement learning um application in this case it's tic-tac-toe so you have this sort of framework available where you can just write the things that are specific to tic-tac-toe game and one thing that you could you know very easily do here is you know swap out different algorithms to see which ones perform perform better so why scholar three um i mean one thing you might ask just in general is why scala so a lot of reinforcement learning code that you see is actually written in python and in fact um one of the things that is in the repo with this library is a lot of examples from the bartow and sudden book which if you look for examples of that code it's pretty much all in python so you might wonder why a scala at all why not python and one answer is um maybe if you've ever used python then the answer is immediately obvious so scala i think is preferable for a lot of reasons so if you look at some of the code one thing that's you know not as easy to do in python is to model something in a way that's easy to understand and use and part of that is maybe um just sort of idiomatic python so if you look look at or or sort of self-taught python engineers so if you look at a lot of the examples um a lot of the code is rewritten over and over again uh for different exam different chapters of the barton sutton book and what that means is that it's hard to compare what the changes are so like if we're learning about temporal difference in one chapter and we're learning about bandits in the other what is that connection so if we model that really well which is a lot easier in scala then it's a lot easier to learn about reinforcement learning and understand what the differences are in these different methodologies um but specifically why scholar three so i have a few of the reasons here but i mean i think by and far opaque types is probably the number one reason so i've always been a fan of value types but we know how dangerous those are um and the nice thing about opaque types especially especially for a library like this is that a lot of times in just to say what opaque types are opaque types are um are like value types in that their types who at compile time are are just primitive types so you don't have the overhead of of types but you have the the type safety that comes along with typing something and in a reinforcement learning library you you have these different things that are all doubles you have rewards you have preferences you have probabilities and it's really important that you differentiate these uh and that you're passing the right thing to each method but it's also important because you'll often have tens of thousands or hundreds of thousands of these in memory that they're efficient and so pig types is a really huge benefit with not having to worry about you know boxing and unboxing happening uh when you don't expect it to um compilation speed um i mean especially when dottie was first coming out was a big deal um and it's still a big deal for reinforcement learning because oftentimes what you're doing is you know you're iterating on these algorithms and you want to compare these algorithms and comparing these algorithms often involves simulations of like you know you might do a hundred simulations and each one has a thousand steps so um you know you have the compile time plus the run time and you really want to make sure that the compile time is really low because um the runtime is already going to be pretty costly uh so just to give an example of an opaque type this is actually a really simple example um one of the things that we track in the reinforcement learning library is how many times you've taken a particular action so this helps with doing things like averaging out over all these actions uh and you know you want a step to be able to increment um but you also want it to be you know low overhead um this is just an example to show how okay types are structured really a better example in the library is probably the probability opaque type where it has a lot of methods on it that allow you to do operations that you would expect to be able to do on probabilities like multiplying probabilities or adding them or something like that um so union types are really nice uh for a couple of reasons one is um when you think about opaque types one of the things about opaque types is they can't inherit from other types or they can't you know inherit a trait or extend a trait so union types are a nice way to be able to to have a single type that let's say your your class can use in this case it's a goal and those um those types in the union are actually opaque types um union types are actually nice for some other reasons so you know in scholar two i used a lot of uh sealed traits with you know case objects to do things like uh enumerations or union types um and i think one of the things that as i iterate on this library more is i'll probably start using union types in a lot of those places where i use sealed traits it's just sort of a habit that i have from scala to but it's a really nice feature um trait parameters are nice so i mean the nice thing i like about trade parameters is that um you know typically i just want to use trades i very rarely want to use abstract classes and i would often have to switch to an abstract class just because i wanted the class to have or the trait to have parameters and not having to make that switch and use trades exactly what i want to is a really nice feature there's a lot of nice syntax features that are really helpful i mean remember that this is for for learning and comparing algorithms this library and so really what you want is you want as simple of syntax as possible so this is just showing off on parameter untippling so normally we would have like a case here um and that can be a little bit confusing for people who aren't familiar with scholar because uh it looks like you're only handling one case um and in i mean in fact you kind of are but with parameter on doubling it's a little bit clearer um what the the function is doing without the the extra verbosity and uh you might think oh you know this is a small change but um you know you really want your code to be as simple as possible especially for something like reinforcement learning because you you really want people to be able to on board to your library very easily and be able to implement new things very easily and compare them with as little fluff as possible another way to think about this is when you're modeling things what you really want to do is you want to model the thing in the world the way that you want to you don't want to have to think i have this model for the thing that i'm i'm modeling how do i implement it in this particular language ideally the the model that you express in the language that you're using uh is is really a really good representation of the model that you have in your head um and so a lot of these um syntax improvements really help uh get there with scholar three and you'll see in the library there are other things like sometimes i use if then instead of you know the parentheses and the curly braces when it's appropriate and it really just helps with the readability and the flow of the code cool so um i'll talk a little bit about next steps um so the library is uh it is in um github and it has a lot of um algorithms available and some documentation but there's some more documentation that needs to be added the other thing is right now uh it's only supporting these tables that we talked about where you store the reward values in these tables but in a lot of cases in reinforcement learning you have so many states or you might even have a continuous state space so storing all these states in a table um is really not possible so there's uh function approximation is a way of handling that and that's something that we'll be implementing i'll be implementing the library shortly there's a few chapters from the barton sutton book in the repository which helps with learning i'll be adding more of those chapters um iterating more on the model representation so you know as i add function approximation these other things really getting the um the interface of the model right is going to be important and so you might see some iterations on that and then as i mentioned you know there's a lot of new skull three features that i'm still getting used to i have some old habits from scala too so i'll be incorporating more of the skull three features into the library as well cool so um like i mentioned i'm a software engineer at twitter our team is hiring um i'm on the experimentation team uh so if you're interested check out the the twitter careers page uh you can find me on twitter at robert j neal my github is githubgithub.com slash robert daniel uh big thanks to aaron for showing off an implementation of this i think it was really helpful um there are a couple references for uh reinforcement learning the barton sutton book that i mentioned it quite a few times is really good there's also a really good youtube um series by david silver on reinforcement learning um and i was going to add some free resources on here but presumably you guys are all familiar with those the the dottie help pages i think have been the biggest resource for me but there's also a lot of good resources out there on the web cool and that's all i got thanks you