ASO Patents

Publication number	WO2023235143A1
Official title	Two-layer bandit optimization for recommendations
Applicant	Apple Inc.
Inventors	Siyong Ma, Puja Das, Debankur Naskar, Chandrasekar Venkataraman, Sofia Nikolakaki
Priority date	May 31, 2022
Filed	May 16, 2023
Published	December 7, 2023
Application	PCT/US2023/022394
Status	Listed as ceased, with anticipated expiration of the international phase in November 2024
Source	patents.google.com/patent/WO2023235143A1

What This Patent Covers and Why It Matters for ASO

Feature it describes: the suggested results section on the App Store search screen, meaning the apps shown before the user has typed anything.

This one is explicitly about an app store. The description states that the search landing page in its example is a landing page for an app store, and it tracks app downloads, re-downloads, manual updates, opens and purchases as the interaction signals inside the suggested results region. No scope caveat is needed.

The mechanism is a multi armed bandit, run in two layers. A bandit is an algorithm for allocating limited attention among options whose payoffs are unknown, balancing exploitation of what already performs against exploration of what has not been tried enough. Applying one to a recommendation slot has a consequence that matters enormously for smaller apps: exploration is structural. The system is designed to give impressions to items with little feedback history, not as a favor but because it cannot learn otherwise.

The patent goes further and describes appending a predetermined number of unranked items, selected by uniform sampling, to the ranked list, explicitly to reduce confirmation bias and maintain diversity. That is a reserved allocation of slots to items that did not earn them.

What follows for practice:

• A brand new app is not invisible to this surface. Under a bandit allocation it receives exploratory impressions by design, which makes the first cohort of users who see it unusually valuable: their behavior determines whether the algorithm keeps showing it.
• The reward is not only the install. Opens, re-downloads, manual updates and purchases are all named as tracked interactions. An app that gets downloaded and never opened is feeding a weak signal into this system.
• The reward estimate is deliberately conservative, computed as a lower confidence bound on the conversion rate distribution using the central limit theorem. Consistency beats a single strong day. Volatile performance is penalized by construction.
• Users are clustered into cohorts by shared interaction history, with traits such as a puzzle game affinity, and a user can belong to several cohorts weighted by affinity strength. You are not competing for one global ranking on this surface. You are competing inside cohorts.
• Diversity is an explicit objective, stated as preventing content fatigue. A slot is not simply awarded to the highest scoring app, which means being the second best fit for a cohort is a viable position.

Two limits on how far to take this. The international application is listed as ceased, so Apple did not carry the PCT route forward as recorded, and the claims section is not reproduced in the published record available through common aggregators, which means the analysis below rests on the abstract and the description rather than on claim language.

Patent Summary

A search interface presents a query input component and a suggested results section. The items in that section are selected on two bases: the likelihood that each selectable item will be selected, and a search session history covering historic selection of each item from prior suggested result regions.

“A search interface is presented with a search query input component and a suggested results section. The suggested results section includes potential search results selected based on a likelihood of selection of each of the selectable items and a search session history corresponding to a historic selection of each of the selectable items from prior suggested result regions.”

WO2023235143A1, abstract

The described implementation splits that selection into two stages. A recall layer runs a more exploratory contextual bandit to narrow the catalog to a candidate set while preserving room for items with little data. A ranking layer runs a more exploitation heavy bandit, using Thompson sampling, to order the candidates. Uniformly sampled unranked items are appended to the result to maintain diversity. Cohort membership determines which items are candidates for a given user.

Detailed Explanation

Why two layers instead of one

A single bandit over a full app catalog is impractical. The number of arms is enormous, most arms have almost no data, and the exploration required to learn about all of them would wreck the user experience.

The two layer design splits the problem by the kind of mistake each layer can afford. The recall layer is allowed to be wrong often because its output is a candidate set, not a recommendation, so it can afford to be exploratory. The ranking layer decides what the user actually sees, so it leans toward exploitation. Exploration is cheap upstream and expensive downstream, and the architecture puts it where it is cheap.

Layer 1: the recall function

The recall layer filters the catalog down to high performing items while preserving exploratory capacity. It computes a conservative reward score from two session level counts described in the patent as S and D.

• S: sessions in which an item was selected and a search query was also submitted
• D: sessions in which an item was selected without a subsequent search query submission

The score is formed as a difference between them, presented in the document as Fcc equals S minus D for a given item, and characterized as a conservative estimate of that item’s performance.

Be careful with this passage. Read literally, subtracting the sessions where a user selected an item and stopped searching would penalize the cleanest success case, which is counterintuitive. The stated objectives of the system include reducing search bar cannibalization, so one reading is that Apple is separating suggestion driven engagement that complements search from suggestion driven engagement that replaces it, and is willing to discount the latter. Another is simply that the variable definitions in the published summary do not map cleanly onto the formula. Both readings are possible from the material available, and anyone presenting either as settled is overstating the record.

What is not ambiguous is the conservatism. The patent describes using the central limit theorem to compute lower confidence bounds on conversion rate distributions. Items are judged on the bottom of their plausible performance range rather than the middle, which systematically favors items with enough data to have a tight distribution, and systematically discounts items whose good average rests on few observations.

Layer 2: the ranking function

The ranking layer orders the recalled items using Thompson sampling. Thompson sampling maintains a probability distribution over each arm’s true reward, draws a sample from each distribution, and plays the arm with the highest draw. Arms with wide distributions, meaning little data, occasionally draw high and get played. Arms with tight, high distributions get played most of the time.

That gives exploration for free without a separate exploration budget, which is why it is the natural choice for the layer that faces the user. The patent describes this layer as exploitation intensive while still surfacing lower feedback items, which is exactly Thompson sampling’s behavior.

On top of that, a predetermined number of unranked items are appended to the ranked list through uniform sampling, stated as a measure against confirmation bias and for diversity. Uniform sampling is the bluntest possible exploration: every candidate has equal probability regardless of performance. Its presence alongside Thompson sampling suggests Apple judged the learned exploration insufficient on its own, which is a reasonable worry in a catalog where the popular items generate the data that keeps them popular.

The arms, and what counts as a reward

The arms are individual catalog items, which in the app store case means apps. The reward is engagement with the suggestion, and the description names the tracked interactions within the suggested results region: downloads, re-downloads, manual updates, opens and purchases.

That list is more interesting than it first looks. Re-downloads and manual updates are signals about an existing relationship between a user and an app, not about acquisition. Including them means the suggested section is partly a re-engagement surface, and that an app with a loyal base has an advantage on it that has nothing to do with new user appeal. Opens matter too, which ties suggestion performance to whether the install was actually used.

Cohorts

Figure 3 covers cohort based item selection. Users are clustered on shared interaction history, common traits are identified, with a puzzle game category affinity given as the example, and each user is assigned to one or more cohorts. Suggested items are then weighted by the strength of that user’s affinity toward each cohort they belong to.

Multi cohort membership with affinity weighting is the part worth absorbing. A user who is 70 percent puzzle and 30 percent productivity does not get two separate lists. They get one list whose composition reflects both memberships in proportion. For an app, this means the addressable population on this surface is not a category but a set of affinity weighted cohorts, and being a strong fit for a niche cohort can be worth more than being a mediocre fit for a broad one.

What the system is optimizing for

Four objectives are described: likelihood of item selection based on historical behavior, diversity to prevent content fatigue, reduced cannibalization of the search bar, and cohort specific relevance.

The cannibalization objective is the unusual one and it says something about how Apple views this surface. The suggested section is not meant to maximize its own engagement. It is meant to help without replacing search, which implies an internal preference for search as the primary path. For anyone allocating effort between ranking for keywords and courting recommendation surfaces, that is a mild argument for keeping search first.

How to use this in practice

• Treat the days after launch as a measurement window that decides your standing, not as a period of low traffic to endure. Exploratory impressions arrive early and the conversion they produce sets the distribution the bandit reasons about.
• Optimize for opens, not only installs. Open events are named as tracked interactions, so onboarding friction is plausibly a recommendation problem and not only a retention problem.
• Prefer steady performance over spikes. A lower confidence bound rewards tight distributions, and a burst driven by a paid campaign widens yours.
• Define your app for a cohort rather than a category. Affinity weighted cohort membership rewards clear fit with a specific behavior pattern.
• Do not budget for this surface. There is no bid, no placement to buy, and no lever except the app’s own engagement record.

Related patents on this site

US20240086412A1 covers personalized recommendations from a different angle. US 2023/0095944 A1 concerns search suggestions, which is the adjacent surface once the user starts typing. US8364694B2 is the 2007 ancestor of all of this, where suggestion ordering was a simple purchase leaderboard.