<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Dimitri Tishchenko on Medium]]></title>
        <description><![CDATA[Stories by Dimitri Tishchenko on Medium]]></description>
        <link>https://medium.com/@koozdra?source=rss-f199217251a9------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*qX5FoTKp2fnyYWqt</url>
            <title>Stories by Dimitri Tishchenko on Medium</title>
            <link>https://medium.com/@koozdra?source=rss-f199217251a9------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 13:39:29 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@koozdra/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Tracking Regret, the Cost of Bad Decisions]]></title>
            <link>https://medium.com/making-change-org/tracking-regret-the-cost-of-bad-decisions-216b19989e39?source=rss-f199217251a9------2</link>
            <guid isPermaLink="false">https://medium.com/p/216b19989e39</guid>
            <category><![CDATA[social-change]]></category>
            <category><![CDATA[reinforcement-learning]]></category>
            <category><![CDATA[multi-armed-bandit]]></category>
            <dc:creator><![CDATA[Dimitri Tishchenko]]></dc:creator>
            <pubDate>Thu, 28 Oct 2021 20:19:27 GMT</pubDate>
            <atom:updated>2021-10-29T00:00:14.467Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*5qwBKJC4sCDxd3Ss9yRWGg.jpeg" /></figure><p>Finding the right <a href="https://medium.com/making-change-org/maximizing-social-change-2795506deca9">share headline</a> for a <a href="https://www.change.org/start-a-petition">petition</a> can mean more engagement, giving it a higher chance of becoming a victory and making a change in the world. At <a href="https://www.change.org/">Change.org</a>, we rely on the decision making of hundreds of thousands of <a href="https://medium.com/making-change-org/maximizing-social-change-2795506deca9"><strong>autonomous learning agents</strong></a> (a.k.a mutli-armed bandits) to select the right headline for each petition per share channel. This article describes how we quantify and evaluate the efficiency with which these agents learn and perform.</p><p>For each petition, we create an autonomous learning agent per share channel. The goal of this agent is to select the best converting (highest engagement) headline from a list of headline variants. Each agent begins without any information about the variants and must discover on its own which variant is the best. This is accomplished by using these variants and observing the results. Over time, the agent should learn which variant is best and use it as much as possible.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ftn7cig55xsBYpRPOFyzXQ.png" /><figcaption>High level data flow diagram of social sharing learning agents</figcaption></figure><p>After a period of observation, the <strong>conversion rates</strong> (the proportion of variant usage to the number of times something rewarding happens with the variant) for the variants become apparent. In our use case, the conversion rate is the number of times a user saw the variant and signed the petition over the number of times a variant is used for a share. The variant with the highest conversion rate is known as the <strong>best variant</strong> and we would have benefited if our agent had used it for all of its decisions. While it can only be calculated in retrospect, determining the best variant is required in order to evaluate the decision-making ability of the agents.</p><p>The decisions that agents make as they choose variants can be broken down into two types. <strong>Good decisions</strong> are ones in which the agent chose to use the best variant. Conversely, <strong>bad decisions</strong> are ones in which the agent chose a variant that is not the best one.</p><p>Each time an agent makes a good decision and selects the highest converting variant, it is acting optimally. For every bad decision, the agent is not acting optimally and incurs regret. <strong>Regret</strong> is a term in reinforcement learning that quantifies how suboptimal a bad decision was. Consider a petition where we have three variants v1, v2 and v3. Variant v1 converts at a high rate, while v2 converts at a medium rate, and v3 has a poor conversion rate. If an agent chose v1 for every decision, it would be acting optimally. Since the agent doesn’t know what the conversion rates are for the variants, it must select suboptimal variants to learn about them. When the agent explores, picking v3 is worse than picking v2 because v2, while not being the best, is still better than v3. Given that conversion rates are numeric we can quantify the amount of regret we accumulate with each bad decision.</p><h3>Epsilon-Greedy vs UCB Exploration Behaviour</h3><p><a href="https://en.wikipedia.org/wiki/Multi-armed_bandit#Approximate_solutions">Epsilon-greedy</a> and <a href="https://lilianweng.github.io/lil-log/2018/01/23/the-multi-armed-bandit-problem-and-its-solutions.html#ucb1">UCB</a> are two methods that can be used by an agent to balance <strong>exploitation</strong> (using the best variant as often as possible) vs <strong>exploration</strong> (picking variants other than the current best to learn about them). When we switched from epsilon-greedy to UCB we saw a decrease in regret. This is because of how epsilon-greedy and UCB differ in the way they behave when they explore variants. When epsilon-greedy explores, it selects a random variant. No information about the variant is taken into account when making the decision of which variant to choose. When UCB selects a variant, it selects the variant that it is most confident about being the best and considers the number of times a variant has been used. This means that very poorly performing variants are used much less frequently than the higher converting variants. Using the example from above, when exploring, epsilon-greedy would use v2 and v3 equally even though it is known that v3 performs very poorly. UCB will use v2 more often than v3 as it takes into account the conversion rate as well as the number of times the variant has been used.</p><h3>Petition Lifecycle — Decision Numbering</h3><p>Each decision made by an agent for a petition can be thought of as a sequence of decisions that can be numbered. For all the petitions that the agents are making decisions for, we can consider the first decision that was made and give it a number, 1. For all the second decisions on the petitions we can give it a number 2 and continue this numbering for each decision. Since our agents are trying to balance exploration and exploitation as they learn about their variants, the first several decisions are going to contain bad decisions because they have to learn about potentially suboptimal variants. As the agents learn about the variants, they begin to explore less often and utilize the best variant, resulting in more good decisions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*vMBhnY1vKHrk4rShPA4iUw.png" /><figcaption>Example of percentage of good to bad decisions (first 3000 decisions)</figcaption></figure><p>With only a small amount of decisions, the agents quickly determine which variant is best for a petition and begin to use that variant more than any others. After 3000 decisions the data becomes noisy as our pool of viral petitions shrinks. Let us zoom in on the first 300 decisions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*EKOzKV2RPtBni6CmRG0i7A.png" /><figcaption>Example of percentage of good to bad decisions (first 300 decisions)</figcaption></figure><p>The first roughly 50 decisions are spent learning about the effectiveness of the variants. After that we see a continuous, but steady, improvement. The initial saw-tooth pattern at the beginning of the process is noteworthy. It is likely caused by UCB entertaining inferior solutions to build confidence about the best variant during learning but further study is needed to confirm that.</p><h3>System Optimality</h3><p>Regret in this system can be interpreted as unrealized signatures for our petitions due to exploration of the variants. We can visualize these unrealized signatures over time and compare that to the number of realized signatures. The following chart gives us a visualization of system optimality.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3Ky6Zh4WZo-P1PGaIKuv7g.png" /><figcaption>Percentage Regret to Reward Over Time</figcaption></figure><p>The chart demonstrates that the system is quite efficient. The number of unrealized signatures hovers in the low single digits, percentage wise, compared to the number of total signatures we receive.</p><h3>Regret by Variant</h3><p>It is also useful to understand the source of regret and if there is a particular variant that is accruing regret.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KXllgvHU3Sk3dGWe6q7Syg.png" /><figcaption>Regret by Variant Over Time</figcaption></figure><p>The chart above indicates that regret is fairly distributed between the three variants. If one of the variants shows a high level of regret, it is a good candidate for removal/replacement.</p><p>The monitoring described in this article demonstrates that the autonomous agents that are making decisions when selecting variants are making good decisions. With this type of monitoring in place, we can have confidence to iterate on the variants that these agents choose from. New variants can be evaluated and we can confirm that our modifications to the variants won’t have adverse reactions to the running system.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=216b19989e39" width="1" height="1" alt=""><hr><p><a href="https://medium.com/making-change-org/tracking-regret-the-cost-of-bad-decisions-216b19989e39">Tracking Regret, the Cost of Bad Decisions</a> was originally published in <a href="https://medium.com/making-change-org">Making Change.org</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Elixir Powered Event Metrics]]></title>
            <link>https://medium.com/making-change-org/elixir-powered-event-metrics-a9c710def7aa?source=rss-f199217251a9------2</link>
            <guid isPermaLink="false">https://medium.com/p/a9c710def7aa</guid>
            <category><![CDATA[elixir]]></category>
            <dc:creator><![CDATA[Dimitri Tishchenko]]></dc:creator>
            <pubDate>Sat, 26 Sep 2020 02:21:47 GMT</pubDate>
            <atom:updated>2020-09-26T05:21:57.114Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/836/1*aLzE54VJglgHuBt5AcY-ew.png" /></figure><p>Knowing what previous actions a user has taken on our site allows for experimentation targeting and custom user interfaces but requires storing data points on the actions of millions of users. The solution we built combines the speed &amp; concurrency of Elixir with the NoSQL capabilities of Postgres. It regulates high volume writes with <a href="https://hexdocs.pm/broadway/Broadway.html">Broadway</a>, stores semi-structured data via JSONB and exposes an API via <a href="https://www.phoenixframework.org/">Phoenix</a> for high volume reads. At Change we call it the Activity Metrics Service.</p><h3>Event Metric Aggregations</h3><p>Let’s say we have a stream of events that represent a social media share by a user. Each event contains a user id and the share channel that was used (eg, Facebook, Whatsapp..). We are going to maintain a record associated with the user id and increment an entry in that record to reflect that a share occurred and on what channel. Associated with every record type we also store a timestamp of last occurrence. This timestamp is updated on every increment. This aggregated share data allows you to answer questions like “How many times has this user shared to facebook and when was the last time that happened?” and “What is this user’s most used share channel?” A typical activity metric looks like:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/512/1*m4KckEuqyVA2fAvKBsUB8g.png" /></figure><p>The service allows for two types of aggregations; simple and scalar. <strong>Simple</strong> metrics record the occurrence of an event. They maintain a count and a last updated timestamp. For example in the data above a simple metric named “share.email” counts the amount of times a user has shared to the email share channel and when that happened last.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/467/1*dkLOxFtqMXnUnE4w2Sd1Dw.png" /></figure><p><strong>Scalar</strong> aggregations allow for recording values that have a number associated with them (eg, a financial transaction amount). These more complex aggregations maintain the count and last updated timestamp, as with simple metrics, and additionally the cumulative sum and the last value seen.</p><p>With these aggregated data points we can answer the questions above. To find the most popular share channel for a user we would find the entry that has the highest count. Similarly to find the most recently used share channel we would find the maximum last_updated entry.</p><h3>The Service</h3><p>The service is written in Elixir. It is deployed to <a href="https://kubernetes.io/">Kubernetes</a> using <a href="https://www.terraform.io/">Terraform</a>. Each Kubernetes pod is behind an AWS elastic load balancer (<a href="https://aws.amazon.com/elasticloadbalancing/">ELB</a>) and hosts a Pheonix endpoint to fetch metrics for given user. Each Kubernetes pod is <a href="https://kubernetes.io/docs/tasks/configure-pod-container/assign-cpu-resource/">limited to one vcpu</a> and has “+sbwt none” and “+S 1” <a href="https://adoptingerlang.org/docs/production/kubernetes/">vm arguments</a> set to limit the number of schedulers started. This flag makes Elixir a <a href="http://blog.plataformatec.com.br/2019/10/kubernetes-and-the-erlang-vm-orchestration-on-the-large-and-the-small/">“better neighbour”</a> when running in Kubernetes alongside other pods (<a href="https://adoptingerlang.org/docs/production/kubernetes/">this is no longer a concern on Erlang 23</a>).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*O2dd1sI7NiJoCaemZf0mQw.png" /></figure><p>Activity Metrics service is an umbrella project with three apps; Metrics API, Metrics Ingestor and Repository. The metrics api is a Phoenix application that exposes an endpoint for looking up metrics for a given user id. Metrics Ingestor is a Broadway application used for processing messages coming from <a href="https://aws.amazon.com/sqs/">AWS SQS</a>. The Repository app uses <a href="https://hexdocs.pm/ecto/Ecto.html">Ecto</a> to communicate with Postgres.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jgAvXiiABnL42OqLfaLaFw.png" /></figure><p>Our message bus consists of an <a href="https://aws.amazon.com/sns/?whats-new-cards.sort-by=item.additionalFields.postDateTime&amp;whats-new-cards.sort-order=desc">SNS</a> topic and a series of SQS queues with filter subscriptions for each service. Messages flow from our front end through the message bus to listening services. When Broadway processes an event from its SQS queue it calls a stored procedure to increment a metric in the user record.</p><p>The metrics are available through a Phoenix API endpoint. The client provides a user id and the service returns a record with metrics for the user or a 404 error if no metrics are available. When building our UI, our front end servers make a call to the server to get metrics for the current user.</p><h3>The Database</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*nTuJgEyCYWLWyycBs8vPrg.png" /></figure><p>We store the activity metrics in Postgres, taking advantage of its NoSQL capabilities to use it as a document store. This is done by using a table with an id, a <a href="https://www.postgresql.org/docs/9.5/functions-json.html">JSONB column</a> and a set of dates to keep track of creation and last modified dates. The id represents the id of the user and is the unique key on the table. The JSONB column is updated through a series of stored procedures that perform atomic upsert increments on the metrics. “Atomic upsert increment”?? Let’s break that down. <strong>Atomic</strong> as in all modifications on the same record are done sequentially. This ensures that we have accurate counts. <strong>Upsert </strong>means that if the record does not exist it is initialized with a value of one and the current date and if it does exist the value is incremented and the date associated with this metric is updated.</p><h3>The Backfill</h3><p>Before we started the service in production we decided it would be most effective with lots of historical data. At the time we had 680 million events in JSON files in S3 representing three years of user share data events. The challenge was to get the data out of S3 and into Postgres as fast as possible. We wrote a back-pressured backfill script that read files from S3 and wrote them to Postgres using a configurable amount of workers. This ran the production RDS cluster at 100% cpu utilization for just over three and a half days as it imported all of the event data from S3. After running the script the database had over 182 million records. All this processing was done from a single pod running as a triggered job in our Kubernetes cluster.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*38ZQwvvpyfvt6JQWp3gbbA.png" /></figure><p>The backfill script follows what Dave Thomas describes as “hungry consumers” in chapter 19 of the excellent book <em>Pragmatic Elixir</em>. A central coordinator Genserver process uses a dynamic supervisor to create a set of worker processes. These process call out to an S3 file lister that is responsible for fetching pages of file paths from an S3 bucket. When initialized, each worker calls out to the S3 lister to receive a file and parses the contents to get a list of events. The same metric incrementing stored procedures that are used by Broadway are called by the backfill script to process each event. When a worker finishes processing a file, it makes a call to get the next file. When the S3 lister has finished with all the files it responds with a special message to stop the worker from asking for more files.</p><p>The flow of data is back-pressured because it follows a pull model. The end consumer dictates the pace of the entire pipeline. If inserts into the database slow down then the workers will slow down and wait for the transactions to complete before asking for additional files to process.</p><p>With this many workers running in parallel, we ran into issues with S3 rate limiting. Luckily <a href="https://hexdocs.pm/ex_aws_s3/ExAws.S3.html">ExAws.S3</a> comes with an exponential backoff retry mechanism that will have workers wait to make S3 calls if the volume of calls is too high. We also found that starting the workers one second apart helped with the initial contention for S3 resources. Since this was a long running backfill the max time for the exponential backoff was set to an hour so that calls would eventually resolve.</p><h3>Performance</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*UpR0OBe4byrO6o7eLuqrCQ.png" /><figcaption>New Relic service response times</figcaption></figure><p>Despite the large amount of records in the database this service has an average response time of 1.2 ms at 10k rpm (requests per minute). During the peak traffic periods of March 2020 the response time was still sub 3ms when the service was handling 40–50 k rpm.</p><h3>Elixir ❤️</h3><p>Elixir was the perfect fit for this service and is starting to become my favourite programming language. The high level abstraction of Broadway allowed us to get this service set up quickly. Using the various primitives of OTP allowed us to create a robust data transfer script that was able to saturate the write capacity of a production AWS RDS cluster enabling the transfer of data at the fastest possible speed with very little code running from a single server.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a9c710def7aa" width="1" height="1" alt=""><hr><p><a href="https://medium.com/making-change-org/elixir-powered-event-metrics-a9c710def7aa">Elixir Powered Event Metrics</a> was originally published in <a href="https://medium.com/making-change-org">Making Change.org</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Our Elixir Bandit Service]]></title>
            <link>https://medium.com/making-change-org/our-elixir-bandit-service-e2b6af6eebc4?source=rss-f199217251a9------2</link>
            <guid isPermaLink="false">https://medium.com/p/e2b6af6eebc4</guid>
            <category><![CDATA[elixir]]></category>
            <category><![CDATA[ab-testing]]></category>
            <category><![CDATA[multi-armed-bandit]]></category>
            <dc:creator><![CDATA[Dimitri Tishchenko]]></dc:creator>
            <pubDate>Tue, 25 Aug 2020 15:30:12 GMT</pubDate>
            <atom:updated>2020-08-25T15:47:40.468Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*J-aBe9gURghphC3Oz3Z6XA.png" /><figcaption>Rays of the Chaos Game</figcaption></figure><p>At Change.org we leverage Elixir to run tens of thousands of parallel <a href="https://medium.com/@koozdra/maximizing-social-change-2795506deca9">multi-armed bandit optimization experiments</a>. The algorithms powering these experiments make decisions about what copy to present to users in various parts of our product. Our bandit service delivers on both of these requirements. Thanks to Elixir, it is able to run an arbitrary number of parallel experiments, automatically deciding which copy to use when, at blazing speed with very few servers.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qauU4GJr78eD8KYKbA_jaA.png" /></figure><p>The bandit service increments counters for <strong>pulls</strong> and <strong>rewards</strong> that occur with the variants that belong to its experiments. The faster the counters are the more up to date information is used when making decisions. When a variant is used we call this a pull. For example, if we use a variant to make a Facebook share, we record a pull for that variant. If something good happens with the variant we call that a reward. For example, if someone signs a petition as a result of clicking through a share that was using a variant in our experiment, that variant is rewarded.</p><p>Our original implementation of this methodology used Redis as a data store and our front end javascript servers accessed it directly. Redis is very fast and has performant atomic counters but, being an in memory database means it’s not very durable. Another downside of the Redis approach was that we had to maintain large ordered sets for ordering and partitioning of experiment lists (i.e. for administrative interfaces). Without performant atomic counters an alternative approach is required.</p><p>For our Elixir-based bandit service we chose Postgres for greater data durability and rich SQL access patterns. The main gotcha of using Postgres is it will lock rows for updates. This makes atomic counters challenging if you have the potential for many updates to the same counter. Updates to the same row will queue and wait for existing updates to finish. With many requests at scale this will cause request queueing as the database struggles to finish all the updates synchronously. The mitigation solution we chose was to emit events in the pull and reward endpoints and use Broadway batching to batch writes to Postgres that would otherwise cause locking. Emitting events and then processing them adds a small delay and means some decisions are made with data that might not be as up to date as it could be. Looking at our pipeline we can see that, on average, processed messages are only 9 seconds old. This delay does not affect our use case and is well worth it for the benefits we get from Postgres in terms of durability and query ability.</p><p>Our EDA (<a href="https://en.wikipedia.org/wiki/Event-driven_architecture">Event Driven Architecture</a>) message bus is currently built using SNS and SQS with filter subscriptions. Each SQS queue contains events of a given type. Services process messages on their queues. The bandit service is a principled EDA service, meaning that it writes to the database only as a result of an event. When a web request is received, the only thing that happens is an SNS message is emitted. Those messages make their way to their respective SQS queues. We use Broadway to process messages from SQS and batch writes to Postgres to avoid row write locking.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*d736Ofb0Zv7d05oZ_KLHjg.png" /><figcaption>Bandit Service Pull/Reward Architecture Diagram</figcaption></figure><p>In production, the bandit service is deployed in <a href="https://docs.aws.amazon.com/eks/latest/userguide/what-is-eks.html">EKS</a> using <a href="https://www.terraform.io/intro/index.html">Terraform</a>. We maintain eight pods in production and have never had to scale further(even during the record traffic levels of March 2020). Each Kubernetes pod sits behind a load balancer and hosts an API and two broadway pipelines, one for each of the events the service is interested in (“pulls” and “rewards”). Deploying these side by side means we can scale to meet the demand of either the API or the queue processing.</p><p>Web response times average 25ms, of which 20 is spent waiting for SNS to guarantee delivery — meaning the Elixir side of the request is only 5ms! In the future we look forward to a specialized message bus provider like Kafka that will have very fast writes.</p><p>We segment our testing space by petition (run an experiment per petition) but the bandit service offers targeting based on a dynamic set of targeting variables. For example if you wanted to segment based on petition and locale, that could be done. There would be an experiment for every petition, locale pair. Segmentation is a powerful tool but if there are too many very small tests, the service will have trouble converging on the optimal variant for each test.</p><p>The scale of running tens of thousands of parallel multi-armed bandit experiments requires a solution that is performant, automated and fast in its decision making. Our bandit service provides a model-free optimization method that can be used in many applications to optimize problems that can be stated in terms of pulls and rewards. Elixir has proven itself to be extremely resilient and highly performant. Integrating Broadway and using its batching feature was easy and intuitive.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e2b6af6eebc4" width="1" height="1" alt=""><hr><p><a href="https://medium.com/making-change-org/our-elixir-bandit-service-e2b6af6eebc4">Our Elixir Bandit Service</a> was originally published in <a href="https://medium.com/making-change-org">Making Change.org</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Maximizing Social Change]]></title>
            <link>https://medium.com/making-change-org/maximizing-social-change-2795506deca9?source=rss-f199217251a9------2</link>
            <guid isPermaLink="false">https://medium.com/p/2795506deca9</guid>
            <category><![CDATA[multi-armed-bandit]]></category>
            <category><![CDATA[ab-testing]]></category>
            <category><![CDATA[social-sharing]]></category>
            <dc:creator><![CDATA[Dimitri Tishchenko]]></dc:creator>
            <pubDate>Sun, 07 Jun 2020 20:01:39 GMT</pubDate>
            <atom:updated>2020-06-08T18:43:08.860Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*P7ce3UpnTdtdWxpf-M41xg.png" /></figure><p>Every day thousands of petitions get created around the world on <a href="https://www.change.org/start-a-petition">Change.org</a>. The most effective way a petition starter can reach an audience is social media sharing. Change assists petition starters by picking the most engaging share headline. With more engagement comes more signatures, which leads to a greater chance of becoming a victory. The virality cycle of most petitions is short lived so there isn’t time to employ traditional A/B testing methodologies. Instead we employ real-time, adaptive <a href="http://incompleteideas.net/book/RLbook2020trimmed.pdf#page=47">multi-armed bandit algorithms</a>.</p><h3>Share Headline Testing</h3><p>When a user shares on social media we can control the copy that appears in the post. For example on Facebook it is possible to customize the share headline and description. In the following example “Can you spare…” and the grey description below are custom text we control when the post is created.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/526/1*q-cWO1rkWw7mOQtJXKlPPQ.png" /></figure><p>From experience we have a set of headline and descriptions that we have found very effective at engaging users to sign the petition.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*DwD2Y9U2ixhUgFCmXEEzJQ.png" /><figcaption>Examples of Facebook share copy post variants</figcaption></figure><p>Consider a set of share headlines (h1, h2, h3, h4).</p><p>One thing we can learn is which share headline is the most effective for all petitions. While this can be an effective approach, it does not take into account the fact that the winning variant could be suboptimal in many instances. To illustrate this point, consider four petitions (p1, p2, p3, p4). The following table shows the conversion rate per petition-headline pair. 0.9 means that there is a 90% chance that a share using a particular headline will result in someone signing the petition (aka a conversion). The conversion rate varies wildly between petitions per headline. Further, there is a balance in the conversion rates. Also in this contrived, worst case scenario, the best headline for any petition is the worst headline for another.</p><figure><img alt="h1 h2 h3 h4 p1: 0.9, 0.7, 0.3, 0.1 p2: 0.7, 0.3, 0.1, 0.9 p3 :0.3, 0.1, 0.9, 0.7 p4: 0.1, 0.9, 0.7, 0.3" src="https://cdn-images-1.medium.com/max/249/1*ivO60pZxv8uNcvYT7yTpdQ.png" /></figure><p>If we ran a typical A/B test we would ignore which petition is currently being used and only look at the petitions on aggregate. Our test results would show:</p><figure><img alt="h1 h2 h3 h4 p: 0.5, 0.5, 0.5, 0.5" src="https://cdn-images-1.medium.com/max/247/1*u2WCat9ynsbskAUkW2RV8A.png" /></figure><p>It appears there is no winner. All of our headlines seem to convert at the same rate. Usually this is not the case and some imbalance exists. In this second example the conversion rate for (p4, h4) is 0.5 instead of 0.3.</p><figure><img alt="h1 h2 h3 h4 p1: 0.9, 0.7, 0.3, 0.1 p2: 0.7, 0.3, 0.1, 0.9 p3 :0.3, 0.1, 0.9, 0.7 p4: 0.1, 0.9, 0.7, **0.5**" src="https://cdn-images-1.medium.com/max/249/1*lQIX9oQ8YgnTJo2-dnTjwQ.png" /></figure><p>If we ran the A/B test now we would get the following:</p><figure><img alt="h1 h2 h3 h4 p: 0.5, 0.5, 0.5, 0.55" src="https://cdn-images-1.medium.com/max/250/1*bNyY7gd0fH1elJuw82OTTw.png" /></figure><p>The imbalance slightly changes the aggregate test and we are able to find a new winner. However, notice that the conversion rate for this headline for p1 is very bad (0.1).</p><p>This would typically be followed up by keeping the winner, brainstorming a new set of share headlines and iterating on the test. There is a limit to this approach as it can only identify imbalances and ignores the petition as a test context.</p><p>We need a system that is able to pick the right share headline per petition. For p1 we want h1, for p2 we want h4. This would involve running a test for each petition. At our scale it is not feasible to have a human operator in the loop. We need this system to be automated.</p><h3>Bandit Optimization</h3><p>Let’s shift our mindset from one of testing to one of optimization. In testing we want to learn the effectiveness of a share headline to know which option we should keep and select for future tests. In an optimization process the variant selection is automated. The difficult task becomes correctly stating the problem.</p><h3>How to Make Decisions</h3><p>Throughout the optimization process we are going to keep track of counters to record our observations. Each time we are asked to select a variant to be used, we will consult our recorded data and make a decision about which variant should be used. We need to balance two things; <strong>exploration</strong> and <strong>exploitation</strong>. Exploitation means that we want to use the best variant we have so that we get the maximum reward. Exploration brings into doubt the fact that our exploitation is using the correct variant. We have to spend time verifying our assumption that the current best variant is indeed the best.</p><p>For every variant of every experiment we are going to maintain two counters.</p><p>First some terminology:</p><p>total number of <strong>pulls</strong>: Increment every time this variant is used</p><p>total number of <strong>rewards</strong>: Increment every time this variant experiences something good</p><p>In our share headline example above pulls are shares and rewards are signature generated from a user clicking the share and signing the petition.</p><p>The data for a typical experiment would then look like:</p><figure><img alt="variant1: pulls: 10 rewards: 5 variant2: pulls: 15 rewards: 7 variant3: pulls: 20 rewards: 18" src="https://cdn-images-1.medium.com/max/219/1*cRhw6dg55knegVD58DmT0Q.png" /></figure><h4>Aside: Badly Incentivized Bandits (<a href="https://towardsdatascience.com/reward-hacking-in-evolutionary-algorithms-c5bbbf42994b">Reward Hacking</a>)</h4><p>An early lesson we learned was that it is very important to know what you want to maximize when designing a bandit. One of our earliest bandits dealt with choosing a petition image from a set of uploaded images. It was pulled on a share and rewarded on a visit. This incentivized the selection of the image to maximize clickthrough rates and created an incentive for the bandits to select click bait images which would not increase signature conversion. We changed the reward to reward on the signature because ultimately that is what we wanted to maximize.</p><h3>E-greedy</h3><p>The simplest decision heuristic available to us is the greedy selection policy. We allocate some initial budget on exploration to gather some numbers and then start using the best variant based on the data we collected during the exploration phase. This is problematic because it is difficult to know how long the initial exploration time should be. If we set it too short we might be exploiting variants that are not the best. In those situations we would like to have had more time to explore and learn about which variant is best.</p><p>To address this issue we are not going to think of exploration as something that needs to be done up front but as an ongoing process that will question our assumption about the best variant. The simplest of these decision making algorithms is E-greedy. With this algorithm we will allocate 10% of our time to exploration and 90% of our time to exploitation. Consider the example above. Each time we have to make a decision about which variant to choose, we will roll a ten sided die (labelled 0–9) if the number is 0 we pick a random variant. Otherwise we will divide our rewards/pulls and pick the best variant. In this case variant 3.</p><p>Following this process will converge on the optimal variant over time which means the best variant will be used more than the others. We have automatic decision making!</p><p>Epsilon greedy has some limitations. If we maintain our ten percent explore selection strategy, we might learn what the best variant is but will continue exploring at a constant rate. We could decay (lessen over time) the explore rate but it would be difficult to know what rate would be optimal. Another issue is that our exploration is a random selection process. The information we have about our variants is not used to guide our exploration decisions.</p><h3>Upper Confidence Bound (UCB)</h3><p>There is a better (smarter?) algorithm that we use. The details of UCB are outside the scope of this article but when this algorithm is asked to select a variant, it uses a formula that tries to pick the variant that is most likely to be the best variant. It might choose a lower performing variant if its confidence about the current information it has about the variant is low. Another advantage of this algorithm is that it is deterministic. It does not require any dice to run which makes testing easier. The best explanation I have seen of <a href="https://youtu.be/sGuiWX07sKw?t=2375">UCB</a> is by David Silver in his excellent <a href="https://www.youtube.com/watch?v=2pWv7GOvuf0&amp;list=PLzuuYNsE1EZAXYR4FJ75jcJseBmo4KQ9-&amp;index=1">course on Reinforcement Learning</a>. UCB will converge on the optimal variant of a test and will only explore sub optimal variants rarely. The disadvantage of having to tune an explore decay for epsilon greedy is taken care of automatically. At Change we started with epsilon greedy bandits but now run all of our bandits using UCB.</p><h3>Maximizing Social Change</h3><p>At Change we use our internally developed bandit service to choose the best copy for each petition at scale across many parts of the product. This scale of optimization has not only made viral events more viral but has also realized gains from the long tail of petitions that get less attention than our more viral petitions. This has lead to more sharing, signing and eventually to petitions becoming successful. Multi-armed bandit optimization is a very general problem formulation with many applications. If you you would like to learn more about bandits and more generally about reinforcement learning, checkout this free textbook <a href="http://incompleteideas.net/book/RLbook2020trimmed.pdf">Reinforcement Learning: An Introduction</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2795506deca9" width="1" height="1" alt=""><hr><p><a href="https://medium.com/making-change-org/maximizing-social-change-2795506deca9">Maximizing Social Change</a> was originally published in <a href="https://medium.com/making-change-org">Making Change.org</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>